Editing Time complexity (section)

== Sub-linear time ==
An algorithm is said to run in '''sub-linear time''' (often spelled '''sublinear time''') if <math>T(n)=o(n)</math>. In particular this includes algorithms with the time complexities defined above. 

The specific term ''sublinear time algorithm'' commonly refers to randomized algorithms that sample a small fraction of their inputs and process them efficiently to [[approximation algorithm|approximately]] infer properties of the entire instance.<ref>{{cite journal | last1 = Kumar | first1 = Ravi | last2 = Rubinfeld | first2 = Ronitt | author2-link = Ronitt Rubinfeld | title = Sublinear time algorithms | journal = [[SIGACT News]] | volume = 34 | issue = 4 | pages = 57–67 | url = http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/kumarR-survey.pdf | year = 2003 | doi = 10.1145/954092.954103| s2cid = 65359 }}</ref> This type of sublinear time algorithm is closely related to [[property testing]] and [[statistics]].

Other settings where algorithms can run in sublinear time include:

* [[Parallel algorithm]]s that have linear or greater total [[Analysis of parallel algorithms#Definitions|work]] (allowing them to read the entire input), but sub-linear [[Analysis of parallel algorithms#Definitions|depth]]. 
* Algorithms that have [[Promise problem|guaranteed assumptions]] on the input structure. An important example are operations on [[data structures]], e.g. [[binary search algorithm|binary search]] in a sorted array.
* Algorithms that search for local structure in the input, for example finding a local minimum in a 1-D array (can be solved in&nbsp;<math>O(\log(n))</math> time using a variant of binary search).&nbsp; A closely related notion is that of [[Local Computation Algorithms (LCA)]] where the algorithm receives a large input and queries to local information about some valid large output.<ref>{{cite book | last1=Rubinfeld | first1=Ronitt |author1-link = Ronitt Rubinfeld | date=2019 | chapter=Local Computation Algorithms | title=Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing | page=3  | doi=10.1145/3293611.3331587 | isbn=978-1-4503-6217-7 }}</ref>