Time Complexity

Time complexity is a measure of the computational work performed by an algorithm, expressed as a function of its input size. Rather than recording elapsed seconds on a particular machine, it counts operations under specified assumptions and describes how that count grows. In computer science, time complexity supports comparisons between algorithms and contributes to computational complexity, which also studies the resources inherently required to solve computational problems. It is distinct from space complexity, the amount of memory required during computation. (aofa.cs.princeton.edu)

Input size and computational models

An analysis begins by defining the input size and the operations being counted. For a sequence, $n$ commonly denotes the number of elements. For a matrix, it may denote the dimension rather than the total number of entries. Problems in graph theory often require separate parameters for vertices and edges. Consequently, a bound involving $n$ is meaningful only when that parameter is clearly defined. (live.ocw.mit.edu)

The model of computation determines the cost of elementary operations. A word-based random-access model treats specified operations on machine-sized values, and access to a memory location, as constant-time operations. A Turing machine instead measures execution through discrete transitions involving its tapes. These models provide explicit foundations for resource accounting rather than exact descriptions of physical hardware. (live.ocw.mit.edu)

Representation also matters. An integer of magnitude $N$ requires approximately $\log_2 N$ bits in binary, so an algorithm performing $N$ iterations can be exponential in the integer’s encoded length. Arithmetic on arbitrarily large integers cannot generally be treated as constant-time: its cost depends on operand length and the operations performed. (ocw.mit.edu)

Asymptotic notation

Time complexity is commonly expressed using big-O notation and related asymptotic bounds. These describe the growth of a nonnegative running-time function $T(n)$, ignoring constant factors and sufficiently small inputs:

• $T(n)\in O(f(n))$ means that $T(n)\leq cf(n)$ for all $n\geq n_0$, for some constants $c>0$ and $n_0$.
• $T(n)\in\Omega(f(n))$ gives an analogous lower bound.
• $T(n)\in\Theta(f(n))$ means that both bounds hold, providing a tight asymptotic characterization. (live.ocw.mit.edu)

For example, $3n^2+7n+12$ belongs to $\Theta(n^2)$. It also belongs to $O(n^3)$, although that upper bound is less informative. Big-O therefore does not necessarily identify an exact growth rate. Nor does it intrinsically mean “worst case”: the notation can describe best-case, average-case, or other running-time functions once those functions have been defined. (live.ocw.mit.edu)

Worst-case, average-case, and amortized analysis

Inputs of equal size can require different amounts of work. Worst-case complexity considers the maximum cost over inputs of a given size, while best-case complexity considers the minimum. Average-case complexity uses an expected value under a specified probability distribution over inputs; without that distribution, “average input” is not a precise mathematical assumption. (aofa.cs.princeton.edu)

For a randomized algorithm, expected running time may instead average over the algorithm’s internal random choices while holding the input fixed. This distinguishes randomness introduced by the algorithm from assumptions about how inputs are generated. (algs4.cs.princeton.edu)

Amortized analysis studies the total cost of a sequence of operations. For example, appending to a dynamically resized array occasionally requires copying all stored elements. With geometric capacity growth, a sequence of appends starting from an empty array has linear total cost, giving constant amortized cost per append. This is a guarantee over operation sequences, not a probabilistic average or a constant worst-case bound for each operation. (cs.princeton.edu)

Common growth rates

Frequently encountered time bounds include:

These examples assume appropriate constant-time elementary operations. Binary search additionally assumes that the sorted input is already accessible; loading or sorting it has a separate cost. For logarithmic bounds, changing between fixed logarithm bases changes only a constant factor. (live.ocw.mit.edu)

A fixed-degree polynomial bound grows more slowly asymptotically than $c^n$ for any fixed $c>1$. Nevertheless, a high-degree polynomial or a large multiplicative constant can make an algorithm impractical at relevant input sizes. (introcs.cs.princeton.edu)

Deriving running-time bounds

Analysis typically combines the cost of operations with their execution frequencies. Sequential stages have additive costs. Nested loops require counting actual iterations rather than merely counting nesting levels: an inner loop executed $i$ times for each outer iteration $i=1,\ldots,n$ performs $n(n+1)/2$ iterations, giving quadratic growth when each iteration costs constant time. (algs4.cs.princeton.edu)

Recursive algorithms often lead to a recurrence relation. In a divide-and-conquer algorithm such as merge sort, two half-sized subproblems and a linear merging stage yield

with a constant-time base case. The resulting bound is $\Theta(n\log n)$. Recurrence analysis must include both recursive calls and the work done outside them. (introcs.cs.princeton.edu)

Interpretation and practical limits

Time complexity characterizes scaling, not an exact execution time. Hardware, implementation choices, memory-access patterns, and input characteristics affect observed performance. Algorithms sharing the same asymptotic bound can therefore differ substantially in speed. Conversely, an algorithm with a better growth rate may be slower on small inputs because of overhead. (introcs.cs.princeton.edu)

The choice of data structure can change operation costs and consequently an algorithm’s overall bound. Empirical measurements complement mathematical analysis by testing performance on specified implementations and workloads; they do not, by themselves, establish a bound for every input size or every possible input. (live.ocw.mit.edu)