Measuring Time Complexity
Suppose you have two algorithms that both correctly sort a list of numbers. One takes a fraction of a second on a list of a million items. The other takes hours. Both are "correct" in the sense of computability theory. Yet one is useless in practice. Classical Turing Machine theory tells us whether a problem is solvable at all. But it says nothing about whether the solution arrives before the sun burns out. Complexity theory fills this gap by asking a sharper question. As the input grows, how does the running time grow with it? This article builds the precise definition of running time for a Turing machine. It shows how to compare algorithms fairly using asymptotic notation. The central design decision has two parts. First, measure running time as a function of input length. Second, take the worst case over all inputs of that length. This choice is not arbitrary. It is chosen specifically so that the resulting theory is robust. It does not depend on the particular encoding of inputs. Nor does it depend on the particular Turing machine variant. It also avoids the vagaries of any one "unlucky" or "lucky" input. In real systems this framework matters greatly. It is the reason we can say, with mathematical confidence, that a sorting routine will still perform acceptably when the input size grows from a thousand to a billion. It also explains why a cryptographic scheme resists brute-force attack even as computers get faster. Database query planners, compiler optimizers, and network routing protocols all rely on this idea. They are built on the assumption that time complexity, once established, predicts real-world scaling behavior. By the end of this article you will be able to state precisely what "the running time of a Turing machine" means. You will define the time complexity class associated with a running time bound. You will also use big-O and small-o notation correctly to compare algorithms. This groundwork is the direct on-ramp to the class P. It also leads directly to the Time Hierarchy Theorem. Both of these depend on the definitions given here being exact.
- Running time of a Turing machine is measured as a function of input length `n`, not input value.
- We take the worst case over all inputs of length `n` — this is what "time complexity" means unless stated otherwise.
- Time complexity function: `t(n) = max { steps M takes on w : |w| = n }`.
- Big-O notation discards constant factors and lower-order terms, focusing on growth rate as `n → ∞`.
- The choice of worst-case + asymptotic + length-based measurement makes complexity theory robust to encoding and machine-model details.
- This machinery is the precise foundation needed to define the class P and to prove the Time Hierarchy Theorem.
The time complexity of a Turing machine is the worst-case number of steps it takes, expressed as an asymptotic function of the input's length.
The idea
A Turing machine `M` computes on inputs, and for any input `w` on which `M` halts, we can count the exact number of steps `M` takes before halting — call this `stepsM(w)`. This is a perfectly well-defined integer for each individual string, but it is not yet a useful measure of "how fast the algorithm is," because it depends on the specific string rather than on the size of the problem being solved. Complexity theory converts this per-string count into a function of a single natural number `n`, the length of the input, by taking the worst case over all inputs of that length. Formally, if `M` is a Turing machine that halts on every input (a decider), its running time or time complexity is the function ``` t : N → N t(n) = max { stepsM(w) : w ∈ Σ, |w| = n } ``` This is a worst-case measure: for each `n`, we look at every possible input string of that exact length and record the largest number of steps `M` ever needs. We say `M` <strong>runs in time `t(n)`</strong>, or `M` is a `t(n)` time Turing machine. Two design choices are baked into this definition and both matter enormously: 1. <strong>Length, not value.</strong> We index by `|w| = n`, the number of symbols in the input, so that the same function `t` applies uniformly across all inputs — a `10`-digit number and a `10`-character string are both "size `10`" inputs, letting us compare running times across problem instances of comparable size regardless of their specific content. 2. <strong>Worst case, not average or best.</strong> Taking the max over all length-`n` inputs guards against surprises: an algorithm that is fast on typical inputs but catastrophically slow on some pathological input of the same length is not considered "fast" by this measure. (Average-case complexity is a separate, harder-to-define notion built on top of a probability distribution over inputs; it is not the default meaning of "time complexity.") Once we have `t(n)`, we almost never care about its exact form — whether the true bound is `3n² + 7n + 2` or `n² + 100` is not interesting; what matters is the <strong>growth rate</strong>. This is where <strong>asymptotic notation</strong> (big-O and small-o) enters. We say `t(n) = O(f(n))` if there exist positive constants `c` and `n₀` such that for all `n ≥ n₀`, ``` t(n) ≤ c · f(n) ``` Big-O gives an <strong>upper bound</strong> on growth rate, ignoring constant factors and lower-order terms; it is the natural language for stating "this algorithm scales at worst like `f(n)`." The companion notation `o(f(n))` (small-o) is a strict* version: `t(n) = o(f(n))` means ``` lim (n→∞) t(n)/f(n) = 0 ``` i.e., `t` grows strictly slower than `f`, in every constant-factor sense — no matter how large a constant `c` you pick, eventually `t(n) < c·f(n)`. This distinction between O (allows matching growth rate) and o (demands strictly slower growth) becomes essential later when comparing time complexity classes and proving separations between them, as in the Time Hierarchy Theorem.
How it works
Computing or bounding the time complexity of a Turing machine `M` is a two-step mental algorithm: first pin down the exact step count on a representative "worst" input pattern, then translate that count into asymptotic notation. The pseudocode below describes the conceptual procedure an analyst follows — this is not something `M` itself does, but the method by which a theorist establishes `M`'s time complexity. ``` procedure ANALYZE-TIME-COMPLEXITY(M):
# M is a Turing machine that halts on every input (a decider)
# Goal: determine t(n), the worst-case step count as a function of n for each n = 0, 1, 2, 3, ...: worst = 0 for each string w of length n over the input alphabet: steps = SIMULATE(M, w) # run M on w, count transitions until halt worst = max(worst, steps) t(n) = worst end for
# t is now defined pointwise; derive a closed form or bound find smallest-order function f(n) such that: there exist constants c, n0 with t(n) <= c * f(n) for all n >= n0 report: M runs in time O(f(n)) ``` ``` procedure SIMULATE(M, w): configure tape with w, head at leftmost cell, state = start state q0 count = 0 while current state is not an accept or reject state: read symbol under head apply M's transition function: write symbol, move head, change state count = count + 1 if count exceeds any theoretical bound and M has not halted:
# only relevant if M's halting on w is in question; for a decider
# this loop always terminates error "M did not halt (contradicts decider assumption)" return count ``` In practice, no one literally enumerates every string of length `n` (there are exponentially many). Instead, analysts reason about the machine's transition structure directly: bound the number of tape passes, the number of head reversals, or the size of the region of tape that can be visited, and multiply these bounds together. The figure below illustrates the core bookkeeping: a single-tape Turing machine processing an input of length `n`, where the running time is governed by how many full left-to-right sweeps of the tape are required.
Complexity & correctness
Why worst-case, and why does it compose additively/multiplicatively the way we expect? The definition `t(n) = max{stepsM(w) : |w| = n}` is a maximum over a finite set (there are exactly `|Σ|ⁿ` strings of length `n` over a finite alphabet `Σ`), so `t(n)` is always well-defined and finite whenever `M` is a decider — no input of length `n` can force `M` into an infinite loop, by the decider assumption, and there are only finitely many such inputs to check. This finiteness is what makes the "max" in the definition meaningful rather than a supremum that might not be attained.
Why asymptotic notation is the right level of abstraction. Two Turing machines that solve the same problem may differ by constant factors due to alphabet size, number of tape symbols, or implementation details (e.g., unary vs. binary encoding of numbers on the tape). A foundational theorem of complexity theory — the linear speedup theorem — states that any Turing machine running in time `t(n)` can be converted into one running in time `ε·t(n) + O(n)` for any constant `ε > 0`, simply by using a larger tape alphabet to pack multiple symbols per cell. This means constant factors are never robust invariants of a problem, only of a particular machine's implementation. Big-O notation is precisely the equivalence class of functions under "differs by a constant factor (and lower-order terms)," so it is the coarsest notation that still respects this speedup theorem — any finer measure (like "exactly `3n²` steps") would be a statement about implementation, not about the problem.
Robustness across reasonable machine models. A second reason worst-case asymptotic time is the right measure: the Church-Turing Thesis variants for efficient computation (the "Extended/Complexity-theoretic Church–Turing Thesis," informally) hold that all "reasonable" deterministic models of computation (multi-tape TMs, RAM machines, etc.) simulate each other with at most a polynomial overhead. For instance, a k-tape Turing machine running in time `t(n)` can be simulated by a single-tape Turing machine in time `O(t(n)²)` — polynomial overhead, not exponential. Consequently, whether a running time is polynomial or exponential in `n` is a model-independent fact, even though the exact polynomial degree may shift between models. This is precisely why the complexity class P (problems solvable in polynomial time) is defined independent of which reasonable machine model you pick, foreshadowing why P is considered a robust, "machine-independent" notion of tractability.
Honesty about the tradeoffs. Worst-case analysis is deliberately pessimistic. Many algorithms with poor worst-case bounds (e.g., quicksort's `O(n²)` worst case, or the simplex method's exponential worst case for linear programming) perform excellently in practice. Complexity theory's worst-case, asymptotic framework buys robustness and universality of guarantees — a proven bound holds for every input, forever — at the cost of sometimes being an overly conservative predictor of real-world performance. Average-case and smoothed analysis exist as complementary frameworks precisely because worst-case time complexity, while foundational, does not tell the whole story.
Worked example
Consider the language ``` A = { 0^k 1^k : k ≥ 0 } ``` and a single-tape Turing machine `M` deciding `A` by repeatedly crossing off matching `0`s and `1`s: ``` M on input w: 1. Scan tape left to right; if a 0 is found to the right of a 1, reject. (Checks the pattern is 01.) 2. Repeat: a. Scan right from the left end; if no unmarked symbols remain, accept. b. Cross off the leftmost unmarked 0. If none remain but unmarked 1s do, reject. c. Scan right to find the leftmost unmarked 1; cross it off. If none remain but unmarked 0s do, reject. d. Return head to the left end of the tape. ``` Let's trace the running time on inputs of length `n`, tracking exact step counts (a scan across `m` cells costs `m` head-movement steps).
| Input `w` (length `n`) | Stage 1 scan | Stage 2 iterations | Cost per iteration | Total steps (approx.) | Accept/Reject |
|---|---|---|---|---|---|
| `ε` (`n=0`) | 0 | 0 | — | O(1) | accept |
| `0011` (`n=4`) | 4 | 2 (crosses 2 zeros, 2 ones) | O(n) each (scan + return) | 2·O(n) + O(n) = O(n) | accept |
| `000111` (`n=6`) | 6 | 3 | O(n) each | 3·O(n) + O(n) = O(n²) | accept |
| `0^k 1^k` (`n=2k`) | n | k = n/2 | O(n) each | (n/2)·O(n) = O(n²) | accept |
| `10` (`n=2`) | 2 | rejects immediately in Stage 1 | — | O(n) | reject |
| `0^k 1^(k+1)` (`n=2k+1`) | n | runs until mismatch found (~k iterations) | O(n) each | O(n²) | reject |
The key observation: for a string of the "hardest" shape `0^k1^k`, each of the `k ≈ n/2` iterations of Stage 2 requires a full left-right-left traversal costing `Θ(n)` steps (scan to find the next `0`, scan to find the next `1`, return to the left end), and there are `Θ(n)` such iterations. This gives ``` stepsM(0^k 1^k) = Θ(n) · Θ(n) = Θ(n²) ``` To get the worst-case function `t(n)`, we must check that no string of length `n` does worse than this. Strings that fail the Stage-1 pattern check (like `10`) terminate in `O(n)` steps — faster. Strings with unequal numbers of `0`s and `1`s but matching the `01` pattern also terminate within one extra iteration of detecting the mismatch, still `O(n²)` at worst since Stage 2 cannot iterate more than `n/2` times before running out of symbols. Hence ``` t(n) = max over all |w| = n of stepsM(w) = Θ(n²) ``` We write `M` runs in time `O(n²)` (and, since the `0^k1^k` family shows this bound is tight, also `Ω(n²)`, so `Θ(n²)` is the exact asymptotic class). Notice this required examining the entire family of inputs of each length, not just one instance — exactly the worst-case discipline the definition demands. A smarter machine using two tapes (or marking with a richer alphabet) can, in fact, decide `A` in `O(n)` time — illustrating that `Θ(n²)` was a property of this particular machine, not of the language `A` itself.
Common pitfalls & traps
| Pitfall | Why it's wrong | Fix | ||
|---|---|---|---|---|
| Measuring time as a function of the input's numeric value rather than its length | A number `N` has length `log N` in binary; conflating the two makes "polynomial time" ill-defined and encoding-dependent | Always index running time by `n = | w | `, the length of the encoded input string |
| Reporting best-case or a single lucky input's step count as "the" running time | Hides catastrophic slow inputs; violates the worst-case convention that defines time complexity | Take the max over all inputs of length `n`, as in the formal definition | ||
| Treating `O(f(n))` as an exact/tight bound | Big-O is only an upper bound; `t(n)=n` is technically `O(n²)` too, which is true but uninformative | State `Θ(f(n))` when both upper and lower bounds match; reserve O for genuine upper-bound-only claims | ||
| Forgetting that unary vs. binary number encoding changes `n` drastically | A number `N` has length `N` in unary but `log N` in binary — an algorithm "polynomial in the numeric value" may be exponential in `n` (this is the trap behind "pseudo-polynomial" algorithms) | Always fix a reasonable (e.g., binary) encoding before discussing polynomial time | ||
| Assuming constant factors distinguish two time complexity classes | The linear speedup theorem shows constant factors can always be shrunk arbitrarily by better tape alphabets | Compare only growth rates (asymptotic classes), never raw constants, when classifying algorithms | ||
| Confusing "the machine examines `n` symbols" with "the machine takes `n` steps" | Head reversals, re-scans, and multiple passes each add separate `Θ(n)` costs that must be summed or multiplied, not assumed away | Explicitly trace passes/iterations, as in the worked example, rather than eyeballing the algorithm description |
Pioneers & history
The formal machinery of time complexity — measuring running time as a function of input length and classifying algorithms by asymptotic growth — emerged from the convergence of computability theory (Turing's 1936 machines) with a new question: not "can this be computed?" but "how fast?" This shift crystallized in the 1960s and early 1970s as researchers sought a rigorous, machine-independent notion of "efficiently computable."
Origins · 1 minJuris Hartmanis and how this was discovered
Juris Hartmanis, alongside Richard Stearns, wrote the 1965 paper "On the Computational Complexity of Algorithms," which introduced the formal definition of running time as a function of input length and proved that allowing more time provably allows solving more problems — the seed of the Time Hierarchy Theorem. This paper is widely regarded as the founding document of computational complexity theory as a distinct field, separate from pure computability theory. Hartmanis and Stearns received the Turing Award in 1993 for this foundational contribution.
Origins · 1 minhow this was discovered
Where this matters
Every time an engineer chooses a sorting algorithm, a database chooses a join strategy, or a compiler chooses a register-allocation heuristic, they are implicitly relying on worst-case asymptotic time complexity bounds to guarantee the system won't degrade unpredictably as data grows. Cloud infrastructure providers publish complexity guarantees (e.g., "amortized O(1) lookup" for hash-based key-value stores) precisely because customers need assurances that hold for all inputs of a given size, not just typical ones. Cryptographic security proofs are built entirely on this framework: a cryptosystem is considered secure if breaking it requires super-polynomial time in the length of the key, a claim that only makes sense once "time complexity as a function of input length, worst case" is pinned down exactly as in this article. Compiler and algorithm textbooks (and courses on Algorithm Design) use exactly this vocabulary — `O(n log n)` sorts, `O(V + E)` graph traversals — trusting that these bounds are robust across machine implementations, a robustness guaranteed by the linear speedup and polynomial-equivalence results discussed above. This same apparatus is the direct prerequisite for defining the class P, the theory of NP-completeness, and the Time Hierarchy Theorem, all of which quantify over the definitions developed here.
Ask the tutor: How does the definition of worst-case time complexity given here get used to formally define the class P, and why does that definition not depend on which specific Turing machine variant we pick?
Why do we take the worst case instead of the average case when defining time complexity?
Worst-case analysis gives a guarantee that holds for every input of a given length, with no exceptions — a property essential for correctness-critical systems like cryptographic protocols or safety-critical control software. Average-case analysis requires specifying a probability distribution over inputs, which is often unknown, application-specific, or manipulable by an adversary (a hostile input could always be chosen to match the "bad" tail of the distribution). Worst-case time complexity is therefore the more conservative, distribution-free, and mathematically robust default; it is what "time complexity" means unless an article explicitly says "average-case" or "expected."
Does time complexity depend on which Turing machine variant (single-tape, multi-tape, nondeterministic) is used?
The exact function `t(n)` can differ across variants, but the broad classification (polynomial vs. exponential, for instance) is remarkably stable. A k-tape Turing machine running in time `t(n)` can be simulated by a single-tape machine in `O(t(n)²)` time — polynomial overhead. This means if a problem is solvable in polynomial time on one reasonable deterministic model, it is solvable in polynomial time on all of them. Nondeterministic machines are the one major exception: simulating an NTM on a DTM currently seems to require exponential overhead, which is exactly the source of the P versus NP question.
What is the difference between O(f(n)) and o(f(n))?
`O(f(n))` (big-O) means the function is bounded above by a constant multiple of `f(n)` for large enough `n` — it allows the function to grow at the same rate as `f(n)`. `o(f(n))` (small-o) is strictly stronger: it requires the ratio `t(n)/f(n)` to tend to zero, meaning `t` grows strictly slower than `f`, for every possible constant factor. For example, `n² = O(n²)` is true, but `n² = o(n²)` is false, while `n = o(n²)` is true. This distinction becomes crucial in proofs like the Time Hierarchy Theorem, which construct problems solvable in time `f(n)` but not in any time `g(n) = o(f(n)/log f(n))`.
Why does the encoding of numbers (unary vs. binary) matter so much for time complexity claims?
An integer `N` requires `Θ(log N)` symbols in binary but `Θ(N)` symbols in unary. An algorithm that takes time linear in the numeric value `N` is therefore linear in `n = |w|` under unary encoding, but exponential in `n` under binary encoding (since `N = 2ⁿ` roughly). This is exactly why some naive primality-testing or dynamic-programming algorithms are called "pseudo-polynomial" — polynomial in the magnitude of the numbers involved, but exponential in the actual bit-length input size. Complexity theory always fixes a reasonable, compact encoding (typically binary) to avoid this trap.
How does this definition of time complexity connect to the class P?
Once running time `t(n)` is precisely defined as worst-case steps as a function of input length, the class P is simply defined as all languages decidable by some Turing machine running in time `O(nᵏ)` for some constant `k`. Because of the polynomial-equivalence results between reasonable machine models (multi-tape simulation costs only a polynomial overhead), this definition of P does not depend on which specific reasonable machine model is chosen — a robustness property that would be meaningless without the exact, worst-case, length-indexed definition of time complexity given here.
Is worst-case time complexity always the most useful measure in practice?
Not always. Many practically important algorithms — quicksort, the simplex method for linear programming, hash table operations with chaining — have poor worst-case bounds but excellent typical performance, which worst-case analysis does not capture. Complementary frameworks like average-case complexity (with a specified input distribution) and amortized analysis (bounding total cost over a sequence of operations) exist precisely to address these gaps. Worst-case time complexity remains the default and foundational measure because it gives distribution-free, adversary-proof guarantees, but a complete engineering picture often requires these complementary tools as well.
What role does the Time Hierarchy Theorem play once we have this definition of time complexity?
Given a precise, worst-case, length-indexed notion of running time, one can ask: does giving a Turing machine strictly more time let it solve strictly more problems? The Time Hierarchy Theorem answers yes, under mild conditions on the time bound (it must be "time-constructible"), by a diagonalization argument that simulates and deliberately disagrees with every machine bounded by the smaller time function. This theorem is only provable — indeed only statable — because "running time as a function of n" has already been pinned down exactly as in this article; it is the direct next step built on this foundation.