Linear time is a running-time bound 
for an algorithm on inputs
of size 
, using big-O notation.
The number of steps is bounded above by 
for some constant 
and all sufficiently large 
.
It is a special case of polynomial time. A matching
lower bound 
gives 
, which is linear
growth in the two-sided asymptotic sense (Cormen et al. 2001, p. 42).
For example, a minimum resolving set of a tree can be found
in linear time, although the metric dimension
decision problem is an NP-complete problem
on graphs of treewidth two
(Benoit 2026).
Linear Time
See also
Algorithm, Big-O Notation, Complexity Theory, Linear Growth, Metric Dimension, Polynomial TimeExplore with Wolfram|Alpha
References
Benoit, T. "Metric Dimension Is NP-Complete on Graphs of Treewidth Two." 15 Oct 2026. https://arxiv.org/abs/2610.21133.Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; and Stein, C. Introduction to Algorithms, 2nd ed. Cambridge, MA: MIT Press, p. 42, 2001.Cite this as:
Weisstein, Eric W. "Linear Time." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/LinearTime.html