(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