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