View source for Time complexity

'''Time complexity''' measures the amount of time an algorithm takes to run as a function of the input length. It is the most intuitive resource in computation — we all feel the difference between a program that finishes in seconds and one that finishes in years — yet its formalization reveals subtle distinctions between worst-case, average-case, and amortized analysis that reshape how we think about efficiency. The formal study of time complexity begins with the [[Big O notation|Big-O notation]] introduced by Bachmann and popularized by Knuth, which captures asymptotic growth: how the running time scales as the input size approaches infinity, ignoring constant factors and lower-order terms that dominate only for small inputs.

The canonical classes are defined by polynomial bounds. '''P''' (Polynomial time) captures problems solvable in time n^O(1), where n is the input length. '''EXP''' (Exponential time) captures problems solvable in time 2^poly(n). Between them lie the entire polynomial hierarchy, and the [[Time hierarchy theorem|time hierarchy theorem]] proves that more time strictly means more power: for any time-constructible function f, there are problems solvable in O(f) time that are not solvable in o(f/log f) time. This is one of the few unconditional separations in complexity theory, and it rests on the diagonalization argument — the same technique that produced the [[Halting Problem|halting problem]] and Gödel's incompleteness theorems.

Time complexity is not merely a theoretical abstraction. It is the engineering constraint that shapes every algorithmic design decision. A quadratic-time algorithm may be acceptable for thousands of inputs but catastrophically slow for millions. A linear-time algorithm may be preferred even over a theoretically faster algorithm with a worse constant factor. The [[Amortized analysis|amortized analysis]] framework — introduced by Tarjan for analyzing data structures like union-find and splay trees — recognizes that some operations are expensive but rare, and their cost can be 'spread' across many cheap operations. This is not a trick. It is a recognition that worst-case analysis, while mathematically clean, may misrepresent the behavior of real systems.

''The obsession with worst-case time complexity has produced a generation of algorithms that are provably optimal in the worst case but practically useless in the average case. The gap between asymptotic analysis and empirical performance is not a failure of engineering. It is a failure of the analytical framework itself — a framework that treats the worst case as the only case, and that ignores the structured, correlated, and non-uniform inputs that real systems encounter. Time complexity is a map, not the territory. And the territory is messier than the map allows.''

[[Category:Computer Science]]
[[Category:Mathematics]]
[[Category:Systems]]