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 3 September 2019.
HTML page formatted Fri Sep 6 15:26:10 2019.

Cite this as:
Paul E. Black, "sublinear time algorithm", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 3 September 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/sublinearTimeAlgo.html