nearlinear

Nearlinear describes time or space complexities that grow almost linearly with the size of the input. In practice, near-linear time is usually expressed as O(n log^k n) for some small k, or more generally O(n polylog n). The exact interpretation depends on the computational model and how the input is encoded. The term signals a performance that is significantly better than many superlinear algorithms but not strictly linear, typically becoming more apparent only for large input sizes.

Common contexts include sorting and graph problems on sparse inputs. Classic comparison-based sorting runs in Theta(n log n) time, which is widely regarded as near-linear for large n. Many graph problems on sparse graphs admit near-linear algorithms in terms of the number of vertices and edges, such as certain minimum spanning tree approaches, approximate schemes, and single-source shortest paths using specialized data structures. Achieving near-linear time often relies on techniques like advanced data structures, recursive decomposition, graph sparsification, and randomized methods.

Limitations: near-linear is an asymptotic notion and depends on the computational model and input encoding. The constants and hidden factors associated with log terms can be significant in practice. Additionally, some problems have proven lower bounds requiring superlinear time in the worst case, so near-linear algorithms are not universally achievable.

See also: linear time, linearithmic time, polylogarithmic time, algorithmic complexity, sparsification.