(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
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 23 December 2004.
HTML page formatted Mon Feb 2 13:10:40 2015.
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: http://www.nist.gov/dads/HTML/sublinearTimeAlgo.html