sublinear time algorithm


Definition: A algorithm whose execution time, f(n), grows slower than the size of the problem, n, but only gives an approximate or probably correct answer.

Generalization (I am a kind of ...)
polynomial time algorithm with k < 1, probabilistic algorithm.

Specialization (... is a kind of me.)
logarithmic time algorithm.

Aggregate parent (I am a part of or used in ...)
quicksort: finding the pivot is a sublinear time algorithm for finding the median.

Note: A sublinear time algorithm doesn't even have the time to consider all the input; it can only sample the input. Binary search is not considered a sublinear time algorithm because the ordering property allows an accurate algorithm in less than linear time.

Author: PEB

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 23 December 2004.
HTML page formatted Wed Mar 13 12:42:46 2019.

Cite this as:
Paul E. Black, "sublinear time algorithm", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 23 December 2004. (accessed TODAY) Available from: