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. 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, 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.Cite this as:
Weisstein, Eric W. "Linear Time." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/LinearTime.html