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 E. Black.

Entry modified 23 December 2004.
HTML page formatted Fri Mar 25 16:20:35 2011.

Cite this as:
Paul E. Black, "sublinear time algorithm", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 23 December 2004. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/sublinearTimeAlgo.html

to NIST home page