(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 E. Black.
Entry modified 23 December 2004.
HTML page formatted Mon Sep 11 09:46:08 2006.
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