sublineartime

Sublineartime is a term used to describe computational time that grows slower than the size of the input. In theoretical computer science, an algorithm operating in sublinear time has running time o(n) with respect to the input size n, and typically relies on random access to a sample of the input rather than reading it in full. In practice, sublinear time is meaningful in models that permit queries to the input, such as read-only arrays or graphs, without requiring a complete scan.

Formally, a sublinear-time algorithm is defined with respect to a model of computation in which the algorithm makes a sequence of queries to the input and performs work between queries. The total number of queries is sublinear in n, and the algorithm's output is determined with high probability by the queried data. Note that sublinear time is not possible for all problems; many problems require reading a substantial portion or all of the input.

Sublinear-time techniques often rely on random sampling, probabilistic estimation, and specialized data structures. Common application areas include property testing (e.g., testing whether a function is monotone), graph property testing, approximate counting, and identifying heavy elements or patterns in large data sets.

Limitations include reliance on assumptions about input distribution, the availability of query access, and probabilistic guarantees rather than exact results. Sublinear-time research continues to explore which properties admit sublinear algorithms, the trade-offs between query complexity and accuracy, and connections to data sketches and streaming models.