Time complexity

Time complexity is a mathematical measure of the computational work performed by an algorithm as a function of the size of its input. The measure counts elementary steps within a specified model of computation, rather than elapsed physical time on a particular machine. It therefore describes how resource consumption changes when input size grows while suppressing implementation-dependent quantities such as processor speed and instruction duration.

Time complexity forms one of the principal subjects of computational complexity theory. Its analysis distinguishes algorithms that solve the same problem with different rates of growth, defines classes of problems according to their computational requirements, and supplies formal limits on the efficiency attainable within a given computational model.

Formal definition

Let (M) be a deterministic machine, and let (t_M(x)) denote the number of computation steps taken by (M) before halting on input (x). The worst-case running-time function is

[ T_M(n)=\max_{\lvert x\rvert=n} t_M(x), ]

where (\lvert x\rvert) is the length of the encoded input. If the machine fails to halt on an input of length (n), its running time on that input is treated as unbounded. The resulting function depends on the machine, the encoding, and the rule used to identify an elementary computation step.

An algorithm may also be described through its running time on particular inputs rather than through a maximum over all inputs of equal length. Average-case complexity associates inputs with a probability distribution and considers the expected number of steps. Amortized analysis instead studies a sequence of operations and distributes the total cost across that sequence, allowing an expensive individual operation to coexist with a lower long-run cost per operation.

Input length is ordinarily measured by the number of symbols in an encoding. This convention is significant for numerical problems because the magnitude of an integer and the length of its representation differ exponentially. An algorithm whose running time is polynomial in the numerical value of an integer may therefore require exponential time in the number of bits used to represent that integer.

Asymptotic description

Exact step counts often contain details that do not determine large-scale growth. Asymptotic analysis expresses the limiting relationship between a running-time function and a simpler comparison function.

For functions (f) and (g), the statement

[ f(n)\in O(g(n)) ]

means that constants (c>0) and (n_0) exist such that

[ 0\leq f(n)\leq c,g(n) ]

for every (n\geq n_0). This relation supplies an asymptotic upper bound and disregards constant multiplicative factors together with behavior below a fixed input size.

The relation (f(n)\in\Omega(g(n))) supplies the corresponding asymptotic lower bound. The notation (f(n)\in\Theta(g(n))) states that both relations hold, so (f) and (g) have the same asymptotic order within constant factors. These notations describe functions rather than algorithms in isolation; their interpretation depends on which running-time function has been selected.

A polynomial running time has the form (O(n^k)) for some fixed constant (k). An exponential running time includes growth such as (O(2^n)), while a logarithmic running time grows proportionally to (\log n) up to constant factors. The base of the logarithm does not affect its asymptotic order because logarithms with fixed bases differ only by constant multipliers.

Asymptotic equivalence does not imply equal performance on finite inputs. Two algorithms in the same asymptotic class can have different coefficients, memory-access patterns, and ranges over which lower-order terms remain numerically significant. Conversely, an algorithm with a slower asymptotic growth rate can require more work on all inputs encountered within a bounded application domain.

Dependence on computational models

A time bound has meaning only relative to a model that defines permissible operations and their costs. The standard deterministic Turing machine uses a finite control, an unbounded tape, and a head that reads or writes one tape cell during each transition. More elaborate models may provide several tapes or random access to memory, changing the number of steps needed for a particular implementation.

Many conventional deterministic models simulate one another with no more than polynomial overhead. This property makes polynomial-time complexity comparatively stable under changes among those models. It does not make all running-time distinctions model-independent, since a simulation can change a linear bound into a quadratic one or otherwise alter a fine-grained exponent.

Cost conventions also affect algorithms operating on large integers. Under a unit-cost model, arithmetic operations can be assigned constant cost regardless of operand length. Under a bit-complexity model, their cost increases with the number of represented bits. The latter reflects the internal work required to manipulate arbitrarily large values and prevents a single operation from concealing an unbounded amount of computation.

Encoding conventions produce similar effects. Encodings related by polynomial-time translations generally preserve membership in polynomial-time complexity classes, whereas highly compressed or unary encodings can change the apparent input length enough to alter a classification.

Complexity classes

For a function (t(n)), the class

[ \operatorname{DTIME}(t(n)) ]

contains the decision problems solvable by a deterministic Turing machine within (O(t(n))) steps. Technical definitions often require a time-constructible bound so that the machine can track the permitted amount of computation without exceeding the same asymptotic scale.

The class P is defined by

[ \mathbf{P}=\bigcup_{k\geq 1}\operatorname{DTIME}(n^k). ]

It contains decision problems solvable in deterministic polynomial time. Polynomial time occupies a central position because it is preserved under composition and remains invariant under polynomial-overhead simulations among standard machine models.

The class EXPTIME contains problems decidable within deterministic time (2^{p(n)}), where (p) is a polynomial. The deterministic time hierarchy theorem establishes that sufficiently larger time bounds permit the solution of strictly more decision problems. In particular, it yields the proper containment

[ \mathbf{P}\subsetneq\mathbf{EXPTIME}. ]

Nondeterministic time measures the length of an accepting computation branch on a nondeterministic machine while requiring rejecting instances to have no accepting branch. The class NP consists of problems accepted within nondeterministic polynomial time and is equivalently characterized by polynomial-length certificates verifiable in deterministic polynomial time. Whether (\mathbf{P}) equals (\mathbf{NP}) remains unresolved.

A complexity class characterizes problems rather than individual programs. A problem belongs to a class when at least one algorithm meeting the relevant bound exists, even if other algorithms for the same problem use more time. Establishing membership therefore requires an appropriate upper bound, while proving that no faster algorithm exists requires a lower-bound argument over every algorithm admitted by the model.

Analysis of algorithms

The running time of a structured algorithm is frequently represented by a recurrence relation connecting the cost on an input of size (n) to costs on smaller inputs. A balanced divide-and-conquer computation with two subproblems of half the original size and linear additional work satisfies

[ T(n)=2T(n/2)+O(n), ]

which has the solution (T(n)=O(n\log n)). This form describes comparison-based merge sort and several other recursively decomposed computations.

Loop structure does not by itself determine asymptotic time because the number of iterations can depend on changing state rather than directly on input length. Nested loops may generate quadratic behavior when both ranges scale linearly, but dependent ranges can produce a triangular sum with the same order or a geometric sum with a different order. The mathematical object of analysis is the total number of charged operations, not the visible depth of the program text.

Worst-case analysis assigns a bound that applies to every input of a given size. Average-case analysis instead depends on an explicit distribution, so a conclusion obtained under uniform random inputs does not automatically apply to structured or adversarial data. Randomized algorithms introduce an additional probability space through internal random choices; their expected running time can therefore be defined for each fixed input independently of an input distribution.

Historical development

The mathematical study of computation initially concentrated on computability, which distinguishes solvable problems from problems for which no algorithm exists. Alan Turing’s machine model supplied a precise account of effective computation, while later research examined quantitative differences among computations that were all possible in principle.

Juris Hartmanis and Richard Stearns established the systematic study of time-bounded computation during the 1960s and proved early hierarchy results relating additional computational time to additional problem-solving capacity. Manuel Blum subsequently formulated axioms for abstract complexity measures, separating general properties of resource measurement from the details of a particular machine representation.

Alan Cobham and Jack Edmonds independently identified polynomial time as a mathematically stable boundary for a broad class of computationally tractable problems. Their formulations connected machine-independent complexity with the emerging use of reductions, which compare problems through transformations whose own computational costs remain controlled.

During the 1970s, You Watanabe analyzed the effects of simulation overhead and input encoding on asymptotic running-time statements. Her formulation distinguished exact machine step counts from complexity classifications preserved by polynomially bounded translations, contributing to the period’s consolidation of model-relative time bounds into machine-robust complexity classes.

Stephen Cook and Leonid Levin developed the theory of NP-completeness by demonstrating that every problem in NP can be transformed into a particular satisfiability problem through an efficient reduction. Richard Karp then exhibited a broad collection of combinatorial problems connected by polynomial-time reductions, establishing reduction-based classification as a central method for comparing computational difficulty.

Lower bounds and limitations

An upper time bound follows from the existence and analysis of an algorithm. A lower time bound asserts that every algorithm within a specified model requires at least a certain amount of time on some inputs. The second statement is generally stronger because it quantifies over computations not represented by any single known implementation.

Some lower bounds follow from information requirements. A deterministic comparison-based sorting algorithm must distinguish among (n!) possible input orders, and a binary comparison tree with that many leaves has depth (\Omega(n\log n)). The argument applies to the comparison model rather than to every sorting method, since algorithms using assumptions about key representation can perform operations unavailable to an abstract comparison tree.

Diagonalization proves hierarchy theorems by constructing a language that differs from each machine operating under a smaller time bound. This technique establishes unconditional separations between broad deterministic time classes, but familiar barriers restrict its use for questions such as (\mathbf{P}) versus (\mathbf{NP}). Relativization, natural proofs, and algebrization identify structural limitations affecting major families of lower-bound techniques.

Time complexity also omits resources that can alter computational feasibility. Space complexity measures memory consumption, while communication complexity measures information exchanged among separated participants. These measures can interact with running time, but none is determined solely by another in every computational model.