NIST

sublinear time algorithm

(definition)

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 Fri Feb 23 10:06:08 2018.

Cite this as:
Paul E. Black, "sublinear time algorithm", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 23 December 2004. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/sublinearTimeAlgo.html