Complexity and Big-O Notation: Measuring Speed as a Function of Input Size

0. Key points

• Complexity is the number of basic operations executed on an input of size $n$; it is not the running time measured in seconds. This abstraction is what makes comparisons independent of machine, language and compiler.
• The statement $f(n) = O(g(n))$ asserts that there exist constants $c > 0$ and $n_0$ such that $f(n) \le c\,g(n)$ for every $n \ge n_0$. Here $O(g)$ is a set of functions, and the equality sign is nothing but a customary abbreviation.
• Growth rates form a hierarchy $1 \prec \log n \prec n^{\varepsilon} \prec n \prec n\log n \prec n^2 \prec 2^n \prec n!$. This is not an intuition but a theorem, provable as a statement about limits.
• Doubling the input size multiplies the cost of a $\Theta(n^2)$ algorithm by $4$, whereas a $\Theta(2^n)$ algorithm gains “all the work it had done so far” again. Making the machine $1000$ times faster raises the largest tractable $n$ for a $\Theta(2^n)$ algorithm by only about $10$.
• For divide-and-conquer recurrences $T(n) = a\,T(n/b) + f(n)$, the master theorem determines the order mechanically.
• The boundary between “solvable in polynomial time” and “only exponential algorithms known” lies at the heart of the P vs NP problem, the central open question of computer science.

1. Motivation: why growth rate rather than seconds

Suppose we want to know which of two programs, A and B, is faster. The naive method is to run them and compare the elapsed seconds. This method has a decisive weakness: what we measured is the speed on that input, on that machine, with that compiler, in that cache state, and nothing guarantees the same ranking tomorrow in a different environment.

Worse, a measurement on small inputs predicts nothing about the behaviour on large ones. Consider two algorithms that sort an array of $n$ elements. Insertion sort performs about $n^2/2$ comparisons in the worst case, while merge sort performs about $n\log_2 n$. For $n = 10$ the counts are $45$ and $33$, barely distinguishable. For $n = 10^6$ they become $5 \times 10^{11}$ and $2 \times 10^7$, a ratio of about $25000$. On a machine performing $10^9$ basic operations per second, the second finishes in $0.02$ seconds while the first takes over eight minutes.

What matters here is not the quality of the implementation but the structure of how the operation count grows as $n$ increases. Better hardware and optimised code buy us, in most cases, a speedup by a constant factor. The choice of algorithm, by contrast, turns $n^2$ into $n\log n$ — a difference no constant factor can close.

We therefore regard the operation count as a function of $n$ and look only at the growth rate, discarding constant factors and finitely many exceptions. It is exactly this coarseness that makes universal, environment-independent comparison possible. Below we first decide what to count (§2), then make the comparison of growth rates precise (§3), prove the resulting hierarchy (§4), and see what happens at realistic scales (§5).

2. Preliminaries: the machine model and complexity

2.1. What counts as one step

Before counting “basic operations” we must decide what a basic operation is. The standard choice is the uniform-cost RAM model (uniform-cost random access machine).

Definition 2.1（The uniform-cost RAM model）

The machine has a sequence of memory cells indexed by addresses $0, 1, 2, \ldots$ together with finitely many registers. Each of the following operations is called a basic operation and is executed in one unit of time.

1. Reading from and writing to a constant, a register, or a memory cell at a specified address
2. Addition, subtraction, multiplication, division and comparison of integers and reals
3. Conditional and unconditional branching

Moreover, a single memory cell is assumed to hold a word of $O(\log n)$ bits, where $n$ is the input size.

The last condition is easy to overlook but essential. Without the restriction to $O(\log n)$ bits per word, one could pack the whole input into a single cell and perform multiple-precision arithmetic in one step, which would license wildly unrealistic algorithms. Under the restriction, on the other hand, the $\log_2 n$ bits needed to index $n$ elements fit into exactly one word, so array index computations take one step — a setting close to a real machine.

Remark 2.2

In the uniform-cost model, multiplying two $k$-digit integers also counts as one step. In cryptography or computer algebra, where huge integers occur, this assumption fails and one uses the logarithmic-cost model, which charges a cost proportional to the number of bits. A complexity claim is meaningless unless the model it is measured in is stated.

2.2. Time and space complexity

Definition 2.3（Worst-case time and space complexity）

For an algorithm $A$ and an input $x$, write $t_A(x)$ for the number of basic operations $A$ executes before halting on $x$, and $s_A(x)$ for the total number of memory cells written to or read from. Define the size $|x|$ of an input $x$ to be the number of words needed to represent $x$. Then

$$T_A(n) = \max_{|x| = n} t_A(x), \qquad S_A(n) = \max_{|x| = n} s_A(x)$$

are called the worst-case time complexity and the worst-case space complexity of $A$.

Note the maximum. Time complexity refers to the least favourable input of size $n$. Consequently $T_A(n)$ is an upper bound guaranteed for every input, once $n$ is fixed.

Time and space are not independent. The next proposition says that space is a “cheaper” resource than time.

Proposition 2.4（Space is bounded by time）

Suppose an algorithm $A$ accesses at most $\kappa$ memory cells per basic operation (in the model of Definition 2.1 one may always take $\kappa \le 3$). Then for every $n$,

$$S_A(n) \le n + \kappa\, T_A(n) .$$

In particular, if $T_A(n) \ge n$ then $S_A(n) = O(T_A(n))$.

Proof（Proposition 2.4）

Fix an input $x$ of size $n$. Every cell accessed by $A$ is either one of the $n$ cells holding the input or a cell accessed during execution. By hypothesis at most $\kappa$ cells are accessed per step, so at most $\kappa\,t_A(x)$ cells are accessed over all $t_A(x)$ steps. Hence $s_A(x) \le n + \kappa\, t_A(x) \le n + \kappa\,T_A(n)$, and taking the maximum over $|x| = n$ gives the first claim.

If $T_A(n) \ge n$ then $n + \kappa T_A(n) \le (1+\kappa) T_A(n)$, so taking $c = 1 + \kappa$ and $n_0 = 1$ in Definition 3.1 yields $S_A(n) = O(T_A(n))$.

∎

The converse fails. One can build algorithms using $O(1)$ space and $\Theta(2^n)$ time at will. The asymmetry “memory can be reused, time cannot” shows itself here.

2.3. Counting in practice

Example 2.5（Counting the comparisons of insertion sort to the end）

Consider insertion sort, which rearranges an array of length $n$ into increasing order.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

Let us count how many times the comparison a[j] > key between elements is evaluated. Fix the outer loop variable $i$; the inner while runs with $j = i-1, i-2, \ldots$ decreasing. Because of short-circuit evaluation no comparison is performed once j >= 0 becomes false, so the number of comparisons equals the number of rounds with $j \ge 0$, that is, at most $i$. This bound is attained exactly when the input is the strictly decreasing sequence $a = (n, n-1, \ldots, 1)$. Indeed, then key is always smaller than every element of $a[0..i-1]$, so the while runs until $j = -1$, giving $i$ comparisons at $j = i-1, \ldots, 0$. Hence the worst-case number of comparisons is

$$\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} .$$

For the same input the number of assignments is $\sum_{i=1}^{n-1}(i+2) = \frac{n(n-1)}{2} + 2(n-1)$, since for each $i$ the statement $a[j+1] = a[j]$ runs $i$ times and reading and writing key accounts for $2$ more. Including loop control changes the total number of basic operations only by a constant factor, so $T(n) = \Theta(n^2)$ (the meaning of $\Theta$ is given in Definition 3.1).

The storage used, beyond the input array, consists of the three words i, j, key, so the additional space is $\Theta(1)$.

Remark 2.6

Besides worst-case complexity one can define average-case complexity, obtained by fixing a probability distribution on inputs and taking the expectation, and best-case complexity, attained on the most favourable input. The best case of insertion sort（Example 2.5） occurs on an already sorted input, with $n-1$ comparisons, that is $\Theta(n)$. Quicksort is $\Theta(n^2)$ in the worst case yet $\Theta(n\log n)$ on average over random permutations (Theorem 5.5［Sorting Algorithms］), and in practice it is this average that governs. See Sorting algorithms for details. Unless stated otherwise, every complexity in this article is worst-case.

3. The notations O, Ω and Θ

3.1. Definitions

From now on $f, g$ denote nonnegative real-valued functions defined on $\mathbb{N} = \{1, 2, \ldots\}$.

Definition 3.1（The notations O, Ω and Θ）

For a function $g$, define the sets of functions $O(g)$, $\Omega(g)$, $\Theta(g)$ by

$$\begin{aligned} O(g) &= \{\, f \;:\; \exists c > 0,\ \exists n_0 \in \mathbb{N},\ \forall n \ge n_0,\ f(n) \le c\,g(n) \,\} \\ \Omega(g) &= \{\, f \;:\; \exists c > 0,\ \exists n_0 \in \mathbb{N},\ \forall n \ge n_0,\ f(n) \ge c\,g(n) \,\} \\ \Theta(g) &= O(g) \cap \Omega(g) \end{aligned}$$

Customarily one writes $f(n) = O(g(n))$ for $f \in O(g)$, read ”$f$ is of order at most $g$”.

The order of the quantifiers is the crux. The constants $c$ and $n_0$ are chosen before $n$; choosing a convenient $c$ separately for each $n$ is not permitted. If this order is broken, then $f \in O(g)$ holds for arbitrary $f$ and $g$ (with $g > 0$), and the notation becomes vacuous.

flowchart LR
A["choose constants c and n0 first"] --> B["then for every n"] --> C["if n is at least n0 then f(n) is at most c·g(n)"]

What the definition of O notation asserts

The notations $o$ and $\omega$ strengthen one quantifier.

Definition 3.2（The notations o and ω）

$$\begin{aligned} o(g) &= \{\, f \;:\; \forall c > 0,\ \exists n_0 \in \mathbb{N},\ \forall n \ge n_0,\ f(n) \le c\,g(n) \,\} \\ \omega(g) &= \{\, f \;:\; \forall c > 0,\ \exists n_0 \in \mathbb{N},\ \forall n \ge n_0,\ f(n) \ge c\,g(n) \,\} \end{aligned}$$

When $f \in o(g)$ we say that $f$ is of strictly smaller order than $g$.

Where $O$ said “for some $c$”, $o$ says “for every $c$”. That $c$ may be taken arbitrarily small means that $f/g$ tends to $0$. The next proposition makes this precise.

3.2. A limit test and the calculus of O

Proposition 3.3（The limit test）

Assume $g(n) > 0$ for all sufficiently large $n$ and that the limit $L = \lim_{n \to \infty} f(n)/g(n)$ exists (possibly $+\infty$). Then:

1. If $0 \le L < \infty$ then $f \in O(g)$.
2. If $0 < L < \infty$ then $f \in \Theta(g)$.
3. If $L = 0$ then $f \in o(g)$.
4. If $L = \infty$ then $f \in \omega(g)$ and $g \in o(f)$.

Proof（Proposition 3.3）

1. Since $L < \infty$, taking $\varepsilon = 1$ in the definition of convergence gives an $n_1$ such that $f(n)/g(n) < L + 1$ for $n \ge n_1$. Multiplying by $g(n) > 0$ yields $f(n) \le (L+1)\,g(n)$. Taking $c = L+1 > 0$ and $n_0 = n_1$ in Definition 3.1 gives $f \in O(g)$.

2. Assume in addition $L > 0$. Taking $\varepsilon = L/2 > 0$ gives an $n_2$ such that $f(n)/g(n) > L - L/2 = L/2$ for $n \ge n_2$, that is, $f(n) \ge (L/2)\,g(n)$. With $c = L/2$ and $n_0 = n_2$ we get $f \in \Omega(g)$, which together with part 1 gives $f \in \Theta(g)$.

3. Assume $L = 0$. Given any $c > 0$, take $\varepsilon = c$ in the definition of convergence: there is an $n_0$ with $f(n)/g(n) < c$, that is $f(n) \le c\,g(n)$, for $n \ge n_0$. As $c$ was arbitrary, Definition 3.2 gives $f \in o(g)$.

4. Assume $L = \infty$. For any $c > 0$, the definition of divergence supplies an $n_0$ with $f(n)/g(n) > c$, that is $f(n) \ge c\,g(n)$, for $n \ge n_0$. Hence $f \in \omega(g)$. Rereading the same inequality as $g(n) \le (1/c) f(n)$ and noting that $c' = 1/c$ ranges over all positive reals as $c$ does, we obtain $g \in o(f)$.

∎

When the limit fails to exist the test is unusable. The $O$ notation itself remains meaningful nonetheless (see Exercise 8.4).

Proposition 3.4（Rules of calculation for O notation）

Let $f, f_1, f_2, g, g_1, g_2, h$ be nonnegative real-valued functions. The following hold.

1. (Reflexivity) $f \in O(f)$.
2. (Transitivity) If $f \in O(g)$ and $g \in O(h)$ then $f \in O(h)$.
3. (Scalar multiples) If $\lambda > 0$ and $f \in O(g)$ then $\lambda f \in O(g)$.
4. (Sums) If $f_1 \in O(g_1)$ and $f_2 \in O(g_2)$ then $f_1 + f_2 \in O(\max(g_1, g_2))$, where $\max(g_1,g_2)$ denotes the pointwise maximum.
5. (Products) If $f_1 \in O(g_1)$ and $f_2 \in O(g_2)$ then $f_1 f_2 \in O(g_1 g_2)$.

Proof（Proposition 3.4）

1. With $c = 1$ and $n_0 = 1$ we have $f(n) \le 1 \cdot f(n)$ for every $n \ge 1$.

2. By hypothesis there are $c_1 > 0, n_1$ with $f(n) \le c_1 g(n)$ for $n \ge n_1$, and $c_2 > 0, n_2$ with $g(n) \le c_2 h(n)$ for $n \ge n_2$. For $n \ge \max(n_1, n_2)$, substituting the second inequality into the first gives $f(n) \le c_1 g(n) \le c_1 c_2 h(n)$ (the direction of the inequality is preserved because $c_1 > 0$). Take $c = c_1 c_2$ and $n_0 = \max(n_1,n_2)$.

3. If $f(n) \le c\,g(n)$ for $n \ge n_0$, multiplying by $\lambda > 0$ gives $\lambda f(n) \le \lambda c\,g(n)$. Replace the constant by $\lambda c$.

4. For $n \ge \max(n_1,n_2)$, using $g_i \le \max(g_1,g_2)$,

$$f_1(n) + f_2(n) \le c_1 g_1(n) + c_2 g_2(n) \le (c_1 + c_2)\max(g_1(n), g_2(n)) .$$

Take the constant to be $c_1 + c_2$.

5. For $n \ge \max(n_1,n_2)$, since $f_1, f_2, g_1, g_2 \ge 0$ the two inequalities may be multiplied, giving $f_1(n) f_2(n) \le c_1 c_2\, g_1(n) g_2(n)$.

∎

Rule 4 is the tool used most often in practice. The everyday reasoning “an algorithm spending $O(n\log n)$ on preprocessing and $O(n^2)$ on the main body costs $O(n^2)$ overall” is nothing but an application of this rule.

Proposition 3.5（The order of a polynomial）

Let $d \ge 0$ be an integer, let $a_0, \ldots, a_d$ be real with $a_d > 0$, and suppose $p(n) = \sum_{i=0}^{d} a_i n^i$ is nonnegative for all sufficiently large $n$. Then $p \in \Theta(n^d)$.

Proof（Proposition 3.5）

First the upper bound. Put $A = \sum_{i=0}^{d} |a_i|$. For $n \ge 1$ we have $n^i \le n^d$ for $0 \le i \le d$, so

$$p(n) \le \sum_{i=0}^{d} |a_i|\, n^i \le \Big(\sum_{i=0}^{d} |a_i|\Big) n^d = A\,n^d .$$

Hence $p \in O(n^d)$ with $c = A$ and $n_0 = 1$.

Now the lower bound. Put $B = \sum_{i=0}^{d-1} |a_i|$ (for $d = 0$ we have $B = 0$ and what follows is trivially true). For $n \ge 1$,

$$p(n) = n^d\Big(a_d + \sum_{i=0}^{d-1} a_i n^{i-d}\Big), \qquad \Big|\sum_{i=0}^{d-1} a_i n^{i-d}\Big| \le \sum_{i=0}^{d-1} |a_i|\, n^{i-d} \le \frac{B}{n} ,$$

where the last inequality uses $n^{i-d} \le n^{-1}$, valid since $i \le d-1$. Taking $n_0 = \lceil 2B/a_d \rceil + 1$, we have $B/n \le a_d/2$ for $n \ge n_0$, whence

$$p(n) \ge n^d\Big(a_d - \frac{a_d}{2}\Big) = \frac{a_d}{2}\, n^d .$$

With $c = a_d/2 > 0$ this gives $p \in \Omega(n^d)$. Combining the two bounds, $p \in \Theta(n^d)$.

∎

3.3. Pitfalls of the notation

Remark 3.6

The equality sign in $f(n) = O(g(n))$ is not symmetric. The statement $n = O(n^2)$ is correct, but one never writes $O(n^2) = n$. Read the sign as "$\in$" or "$\subseteq$", from left to right. An occurrence of $O(\cdot)$ in the middle of a formula stands for “some function satisfying that condition”. For instance,

$$\sum_{i=1}^{n} i = \frac{n^2}{2} + O(n)$$

means “the difference between the left-hand side and $n^2/2$ is a function belonging to $O(n)$”. This convention was codified by Knuth (reference [2]).

Remark 3.7

Inside $O$ notation the base of a logarithm need not be written. By the change-of-base formula $\log_a n = \log_b n / \log_b a$, the functions $\log_a n$ and $\log_b n$ differ only by a positive constant factor, so $\Theta(\log_a n) = \Theta(\log_b n)$. However, as $2^{\log_2 n} = n$ versus $2^{\log_{10} n} = n^{0.301\ldots}$ shows, once the logarithm sits in an exponent the difference of base is no longer a constant factor. The base may be dropped inside $O$ only when the logarithm appears as a multiplicative factor.

Caution

The $O$ notation hides constant factors. A $\Theta(n\log n)$ algorithm with constant $1000$ loses to a $\Theta(n^2)$ algorithm with constant $1$ up to roughly $n \le 10^4$. Indeed, many standard-library sorts switch to insertion sort on subarrays of at most a few dozen elements. Asymptotic superiority and superiority at the $n$ in front of you are different questions.

4. The hierarchy of growth rates

The intuitions ”$\log n$ is far smaller than $n$” and “an exponential is far larger than a polynomial” are made precise by the following theorem. We first prove the underlying lemma.

Lemma 4.1（Exponentials beat polynomials）

Let $c > 1$ and $k \ge 0$ be real. Then, as a limit in the real variable $x$,

$$\lim_{x \to \infty} \frac{x^k}{c^{\,x}} = 0 .$$

Proof（Lemma 4.1）

We first treat the case in which $x$ runs through the natural numbers $n$. Since $c > 1$ we may write $h = c - 1 > 0$. Put $m = \lceil k \rceil + 1$, so that $m > k$. By the binomial theorem, for $n \ge m$,

$$c^{\,n} = (1+h)^n \ge \binom{n}{m} h^m = \frac{n(n-1)\cdots(n-m+1)}{m!}\,h^m \ge \frac{(n-m+1)^m}{m!}\,h^m$$

(here we used that each factor $n, n-1, \ldots, n-m+1$ is at least the smallest one, $n-m+1$). If moreover $n \ge 2m$, then $n - m + 1 > n - m \ge n/2$, so

$$\frac{n^k}{c^{\,n}} \le \frac{m!\; n^k}{h^m (n/2)^m} = \frac{m!\,2^m}{h^m}\; n^{\,k-m} .$$

Since $m > k$ the exponent $k - m$ is negative and the right-hand side tends to $0$ as $n \to \infty$. As $n^k/c^n \ge 0$, the squeeze theorem gives $\lim_{n\to\infty} n^k/c^n = 0$.

Now the real variable case. For $x \ge 1$ put $n = \lfloor x \rfloor + 1$, so that $x \le n$ and $n - 1 \le x$. Since $k \ge 0$ and $c > 1$,

$$\frac{x^k}{c^{\,x}} \le \frac{n^k}{c^{\,n-1}} = c\cdot\frac{n^k}{c^{\,n}} .$$

As $x \to \infty$ we have $n \to \infty$, and by the previous paragraph the right-hand side tends to $0$. Hence $\lim_{x\to\infty} x^k/c^x = 0$.

∎

Theorem 4.2（The hierarchy of growth rates）

Let $a > 0$, $\varepsilon > 0$, $k \ge 0$ and $c > 1$ be arbitrary reals. Then

$$(\log_2 n)^a \in o(n^{\varepsilon}), \qquad n^k \in o(c^{\,n}), \qquad c^{\,n} \in o(n!) .$$

In particular, taking $\varepsilon = 1$, $a = 1$ and $c = 2$, the functions $\log_2 n$, $n$, $2^n$, $n!$ are of strictly increasing order in this sequence.

Proof（Theorem 4.2）

First claim. Put $t = \log_2 n$, so that $n = 2^t$ and $t \to \infty$ as $n \to \infty$. Then

$$\frac{(\log_2 n)^a}{n^{\varepsilon}} = \frac{t^a}{2^{\varepsilon t}} = \frac{t^a}{(2^{\varepsilon})^{t}} .$$

Since $\varepsilon > 0$ we have $2^{\varepsilon} > 1$, so applying Lemma 4.1 with $c = 2^{\varepsilon}$, $k = a$ and $x = t$ shows that this ratio tends to $0$. By part 3 of Proposition 3.3, $(\log_2 n)^a \in o(n^{\varepsilon})$.

Second claim. Applying Lemma 4.1 directly with $x = n$ gives $n^k/c^n \to 0$, and again part 3 of Proposition 3.3 yields $n^k \in o(c^n)$.

Third claim. Put $m = \lceil 2c \rceil$. For $n > m$ we may factor

$$\frac{c^{\,n}}{n!} = \frac{c^{\,m}}{m!}\prod_{j=m+1}^{n} \frac{c}{j} .$$

Since $j \ge m+1 > 2c$, each factor satisfies $c/j < 1/2$, so the product is at most $(1/2)^{\,n-m}$. Hence

$$0 \le \frac{c^{\,n}}{n!} \le \frac{c^{\,m}}{m!}\left(\frac{1}{2}\right)^{n-m} ,$$

and the right-hand side tends to $0$ as $n \to \infty$ (here $c$ and $m$ are constants not depending on $n$). By the squeeze theorem $c^n/n! \to 0$, that is, $c^n \in o(n!)$.

∎

The first claim says that however small $\varepsilon > 0$ is chosen, $n^{\varepsilon}$ eventually exceeds $(\log n)^{100}$: logarithms grow that slowly. The second says that $1.001^n$ eventually exceeds $n^{1000}$: exponentials grow that fast. These two facts are the source of the dramatic differences seen in the next section.

Representative growth rates (the vertical axis is truncated at 100)

5. Reading the main complexity classes

5.1. The doubling rule

The handiest way to grasp the character of each class is to ask what happens to the running time when the input size is doubled.

Proposition 5.1（The ratio under doubling of the input）

Let $\alpha > 0$ and $\beta$ be constants and $k > 0$ real. The following hold.

1. If $T(n) = \alpha$ then $T(2n)/T(n) = 1$.
2. If $T(n) = \alpha \log_2 n + \beta$ then $T(2n) - T(n) = \alpha$ (the difference, not the ratio, is constant).
3. If $T(n) = \alpha n^{k}$ then $T(2n)/T(n) = 2^{k}$.
4. If $T(n) = \alpha n \log_2 n$ then $T(2n)/T(n) = 2\left(1 + \dfrac{1}{\log_2 n}\right)$, which tends to $2$ as $n \to \infty$.
5. If $T(n) = \alpha\, 2^{n}$ then $T(2n)/T(n) = 2^{n}$.

Proof（Proposition 5.1）

Each case is a direct substitution.

1. $T(2n)/T(n) = \alpha/\alpha = 1$.
2. $T(2n) - T(n) = \alpha(\log_2 2n - \log_2 n) + (\beta - \beta) = \alpha \log_2 2 = \alpha$.
3. $T(2n)/T(n) = \alpha (2n)^k / (\alpha n^k) = 2^k n^k / n^k = 2^k$.
4. $T(2n)/T(n) = \dfrac{\alpha \cdot 2n \log_2 2n}{\alpha\, n \log_2 n} = 2\cdot\dfrac{\log_2 n + 1}{\log_2 n} = 2\left(1 + \dfrac{1}{\log_2 n}\right)$. As $n \to \infty$ we have $1/\log_2 n \to 0$, so the ratio tends to $2$.
5. $T(2n)/T(n) = \alpha 2^{2n}/(\alpha 2^{n}) = 2^{2n-n} = 2^{n}$.

∎

Claim 5 expresses the horror of exponential time in a single line. Having solved an instance with $n = 40$, moving on to $n = 80$ multiplies the time by $2^{40} \approx 1.1\times 10^{12}$.

Remark 5.2

Proposition 5.1 is a statement about functions of exactly those forms; the hypothesis $T \in \Theta(n)$ alone does not imply $T(2n)/T(n) \to 2$. For a counterexample take $T(n) = n\,(2 + \sin n)$. Since $1 \le 2+\sin n \le 3$ we have $T \in \Theta(n)$, yet $T(2n)/T(n) = 2(2+\sin 2n)/(2+\sin n)$ oscillates between $2/3$ and $6$ and does not converge. Because $\Theta$ discards constant factors, it does not pin down the limit of the ratio.

5.2. The numbers

Example 5.3（Operation counts and running times in practice）

Assume a machine performing $10^9$ basic operations per second. The operation counts are as follows.

$n$	$\log_2 n$	$n$	$n\log_2 n$	$n^2$	$2^n$
$10$	$3.3$	$10$	$33$	$10^{2}$	$1.0\times10^{3}$
$100$	$6.6$	$100$	$664$	$10^{4}$	$1.3\times10^{30}$
$10^{3}$	$10.0$	$10^{3}$	$1.0\times10^{4}$	$10^{6}$	astronomical
$10^{6}$	$19.9$	$10^{6}$	$2.0\times10^{7}$	$10^{12}$	astronomical
$10^{9}$	$29.9$	$10^{9}$	$3.0\times10^{10}$	$10^{18}$	astronomical

Translated into time:

$T(n)$	$n = 10^{6}$	$n = 10^{9}$
$n$	$0.001$ s	$1$ s
$n\log_2 n$	$0.02$ s	$30$ s
$n^2$	$17$ min	$32$ years

Look at the $n\log_2 n$ row. Even at $n = 10^9$ the factor $\log_2 n$ is only $30$, so $n\log n$ is at most thirty times $n$. Over the range of realistic input sizes, $\Theta(n\log n)$ is barely distinguishable from $\Theta(n)$. This is why $\Theta(n\log n)$ algorithms such as comparison sorting and the fast Fourier transform are treated as “essentially linear”. The same applies to $\Theta(\log n)$: as $n$ grows a hundred-million-fold from $10$ to $10^9$, the value of $\log_2 n$ grows only ninefold, from $3.3$ to $29.9$. That is why binary search appears to finish instantly regardless of the number of elements (see Theorem 3.3［探索アルゴリズム］ and Search algorithms).

Look at the exponential side as well. Performing $2^{50} \approx 1.1\times10^{15}$ operations takes about $13$ days, and $2^{100} \approx 1.3\times10^{30}$ operations about $4\times10^{13}$ years, roughly $2900$ times the age of the universe (about $1.4\times10^{10}$ years). Factorials grow even faster: $20! \approx 2.4\times10^{18}$ corresponds to about $77$ years.

5.3. A faster machine will not save us

The essential difficulty of exponential time is clearest in the following comparison.

Example 5.4（What if the machine becomes 1000 times faster）

We compare the largest $n$ that can be handled within one second on a machine performing $10^9$ operations per second and on one performing $10^{12}$.

$T(n)$	$10^{9}$ ops/s	$10^{12}$ ops/s	change
$n$	$10^{9}$	$10^{12}$	$\times 1000$
$n\log_2 n$	$4.0\times10^{7}$	$2.9\times10^{10}$	about $\times 730$
$n^2$	$3.2\times10^{4}$	$10^{6}$	about $\times 31.6$
$n^3$	$10^{3}$	$10^{4}$	$\times 10$
$2^n$	$29$	$39$	$+10$

Let us verify the last row. Solving $2^{n} = t$ gives $n = \log_2 t$, so multiplying $t$ by $1000$ increases $n$ by $\log_2 1000 = 9.97$, that is, by about $10$. This is a general fact independent of the machine’s speed: for $T(n) = \alpha\,c^{n}$ the increase is $\log_c 1000$.

In the $n^2$ row the improvement is a factor $\sqrt{1000} = 31.6$, in the $n^3$ row a factor $1000^{1/3} = 10$ — that is, the reciprocal power of the exponent. In general, for $T(n) = \alpha n^{k}$, a machine $s$ times faster handles $n$ larger by a factor $s^{1/k}$.

The conclusion is unambiguous. For polynomial time, advances in hardware help; for exponential time, they hardly help at all. The only way through the exponential wall is a better algorithm.

Example 5.5（From brute force to dynamic programming）

Given $n$ positive integers $w_1, \ldots, w_n$ and a target $W$, decide whether some subset sums to exactly $W$ (the subset-sum problem). Brute force enumerates all subsets, examining $2^n$ of them, for a total of $\Theta(2^n \cdot n)$. For $n = 40$ this is $2^{40} \times 40 \approx 4.4\times10^{13}$ operations, about $12$ hours on a machine doing $10^9$ operations per second.

By contrast, dynamic programming that fills a table $b[i][w]$ recording whether the sum $w$ is attainable from the first $i$ items costs only $\Theta(nW)$. For $n = 40$ and $W = 10^4$ that is $4\times10^5$ operations, or $0.0004$ seconds — a speedup of more than thirty million, obtained not by changing the machine but simply by no longer recomputing the same partial sums over and over (recurrences of this shape and their complexity are treated in Corollary 6.4［動的計画法］; see Dynamic programming).

Note that $\Theta(nW)$ is not polynomial in the input size. Representing $W$ requires $\log_2 W$ bits, so $W$ can be exponentially large in the input size. Complexities of this kind are called pseudo-polynomial time.

5.4. The complexity of data structures

The same operation can have different complexity depending on the data structure. Here are the worst-case complexities of the standard structures, with $n$ the number of stored elements.

operation	unsorted array	sorted array	linked list	balanced BST	hash table
search for a value	$\Theta(n)$	$\Theta(\log n)$	$\Theta(n)$	$\Theta(\log n)$	avg. $\Theta(1)$ / worst $\Theta(n)$
insertion	$\Theta(1)$ (at the end)	$\Theta(n)$	$\Theta(1)$ (position known)	$\Theta(\log n)$	avg. $\Theta(1)$
deletion	$\Theta(n)$ (search included)	$\Theta(n)$	$\Theta(1)$ (position known)	$\Theta(\log n)$	avg. $\Theta(1)$
retrieval of the minimum	$\Theta(n)$	$\Theta(1)$	$\Theta(n)$	$\Theta(\log n)$	$\Theta(n)$

There is no universally best structure. A sorted array searches quickly but requires shifting everything on insertion, while a linked list inserts quickly but needs $\Theta(k)$ time to reach the $k$-th element (Proposition 4.2［Fundamental Data Structures］). One decides what should be fast first, and chooses the structure afterwards. The definitions of these structures and the proofs of these complexities are treated in Fundamental data structures.

Remark 5.6

The entry ”$\Theta(1)$ for appending to an unsorted array” assumes there is spare capacity. When the capacity is exhausted, a new region is allocated and all elements are copied, so that particular operation costs $\Theta(n)$. If, however, the capacity is doubled each time it runs out, then starting from capacity $1$ and performing $n$ insertions, copying occurs only when the number of elements is $1, 2, 4, \ldots, 2^{k}$ with $2^{k} < n$, and the total number of copies is

$$1 + 2 + 4 + \cdots + 2^{k} = 2^{k+1} - 1 < 2n .$$

Since the total cost of $n$ insertions is $O(n)$, the average per operation is $O(1)$. Complexity averaged over a whole sequence of operations in this way is called amortised complexity (stated as a theorem, this estimate is Theorem 3.3［Fundamental Data Structures］). It is a different notion from the worst-case complexity of an individual operation, and the two should be kept apart.

6. Divide and conquer: from a recurrence to an order

The complexity of a recursive algorithm appears as a recurrence. For merge sort, an array of length $n$ is split in half, the halves are sorted recursively, and merging takes $\Theta(n)$ time, giving $T(n) = 2\,T(n/2) + \Theta(n)$ (Theorem 4.2［Sorting Algorithms］). Recurrences of this shape are solved at a stroke by the following theorem.

Theorem 6.1（The master theorem）

Let $a \ge 1$ and $b > 1$ be real, let $d > 0$ be a constant, and let $f$ be a positive-valued function defined on the powers of $b$. Suppose the function $T$ satisfies

$$T(1) = d, \qquad T(n) = a\,T(n/b) + f(n) \quad (n = b^{k},\ k \ge 1) .$$

With $n$ ranging over the powers of $b$, the following hold.

1. If $f(n) = O\!\left(n^{\log_b a - \varepsilon}\right)$ for some $\varepsilon > 0$, then $T(n) = \Theta\!\left(n^{\log_b a}\right)$.
2. If $f(n) = \Theta\!\left(n^{\log_b a}\right)$, then $T(n) = \Theta\!\left(n^{\log_b a}\log n\right)$.
3. If $f(n) = \Omega\!\left(n^{\log_b a + \varepsilon}\right)$ for some $\varepsilon > 0$ and, in addition, there is a constant $0 < c < 1$ with $a\,f(b^{k-1}) \le c\,f(b^{k})$ for all $k \ge 1$ (the regularity condition), then $T(n) = \Theta(f(n))$.

Proof（Theorem 6.1）

Let $n = b^{k}$. Unfolding the recurrence $k$ times gives

$$T(n) = a^{k} T(1) + \sum_{j=0}^{k-1} a^{j} f\!\left(\frac{n}{b^{j}}\right)$$

(by induction on $k$: for $k=0$ both sides equal $T(1)$, and if the identity holds for $k$, substituting it into $T(b^{k+1}) = aT(b^{k}) + f(b^{k+1})$ gives it for $k+1$). Here

$$a^{k} = a^{\log_b n} = \left(b^{\log_b a}\right)^{\log_b n} = \left(b^{\log_b n}\right)^{\log_b a} = n^{\log_b a} ,$$

so the first term is $d\,n^{\log_b a}$. Since $f > 0$, we always have $T(n) \ge d\,n^{\log_b a}$. It remains to estimate the sum $\Sigma = \sum_{j=0}^{k-1} a^{j} f(n/b^{j})$.

Case 1. By hypothesis there is a $C > 0$ with $f(m) \le C\,m^{\log_b a - \varepsilon}$ for all sufficiently large powers $m$ of $b$. Then

$$\Sigma \le C \sum_{j=0}^{k-1} a^{j}\left(\frac{n}{b^{j}}\right)^{\log_b a - \varepsilon} = C\,n^{\log_b a - \varepsilon} \sum_{j=0}^{k-1} a^{j}\, b^{-j(\log_b a - \varepsilon)} .$$

Since $b^{-j\log_b a} = a^{-j}$, we have $a^{j} b^{-j(\log_b a - \varepsilon)} = (b^{\varepsilon})^{j}$, and the formula for a geometric series gives

$$\sum_{j=0}^{k-1} (b^{\varepsilon})^{j} = \frac{b^{\varepsilon k} - 1}{b^{\varepsilon} - 1} < \frac{n^{\varepsilon}}{b^{\varepsilon} - 1}$$

(using $b^{\varepsilon k} = (b^{k})^{\varepsilon} = n^{\varepsilon}$). Hence $\Sigma < \dfrac{C}{b^{\varepsilon}-1}\,n^{\log_b a}$ and $T(n) = O(n^{\log_b a})$. The lower bound is the inequality $T(n) \ge d\,n^{\log_b a}$ noted above, so together $T(n) = \Theta(n^{\log_b a})$.

Case 2. By hypothesis there are $c_1, c_2 > 0$ with $c_1 m^{\log_b a} \le f(m) \le c_2 m^{\log_b a}$. Since $a^{j}(n/b^{j})^{\log_b a} = a^{j} n^{\log_b a} a^{-j} = n^{\log_b a}$, every term of the sum lies between $c_1 n^{\log_b a}$ and $c_2 n^{\log_b a}$. There are $k = \log_b n$ terms, so

$$c_1\,n^{\log_b a} \log_b n \le \Sigma \le c_2\,n^{\log_b a}\log_b n .$$

As $\log_b n$ and $\log n$ differ only by a positive constant factor (Remark 3.7), $\Sigma = \Theta(n^{\log_b a}\log n)$. The first term $d\,n^{\log_b a}$ is absorbed into this, so $T(n) = \Theta(n^{\log_b a}\log n)$.

Case 3. From the regularity condition one proves $a^{j} f(n/b^{j}) \le c^{\,j} f(n)$ by induction on $j$. Indeed, for $j = 0$ this is an equality. Assuming it for $j$ and applying the regularity condition at $n/b^{j}$, we have $a f(n/b^{j+1}) \le c f(n/b^{j})$, whence

$$a^{j+1} f(n/b^{j+1}) = a^{j}\cdot a f(n/b^{j+1}) \le a^{j}\, c\, f(n/b^{j}) \le c\cdot c^{\,j} f(n) = c^{\,j+1} f(n) .$$

Therefore, since $0 < c < 1$,

$$\Sigma \le f(n) \sum_{j=0}^{k-1} c^{\,j} < \frac{f(n)}{1-c} .$$

Moreover, the hypothesis $f(n) = \Omega(n^{\log_b a + \varepsilon})$ gives a $c_3 > 0$ such that $n^{\log_b a} \le \dfrac{f(n)}{c_3\,n^{\varepsilon}} \le \dfrac{f(n)}{c_3}$ for all sufficiently large $n$, so the first term is also $O(f(n))$. Hence $T(n) = O(f(n))$. On the other hand, keeping only the $j = 0$ term of the expansion gives $T(n) \ge f(n)$, so $T(n) = \Omega(f(n))$, and therefore $T(n) = \Theta(f(n))$.

∎

Remark 6.2

In real algorithms $n/b$ need not be an integer, and the recurrence takes the form $T(n) = a\,T(\lfloor n/b\rfloor) + f(n)$. It is known that the same conclusions as in Theorem 6.1 hold for this floor-function version; the proof is in Chapter 4 of Cormen et al. (reference [1]). That book also states the regularity condition in the weaker form “for all sufficiently large $n$”. Even in this weaker form the conclusion is unchanged, since at most $\log_b n_0 + 1$ terms violate the condition and each of them is $O(n^{\log_b a}) = O(f(n))$. Techniques for recurrences to which the master theorem does not apply are treated in the Appendix.

Example 6.3（Applying the master theorem）

(a) Merge sort. For $T(n) = 2\,T(n/2) + \Theta(n)$ we have $a = 2$, $b = 2$, $f(n) = \Theta(n)$. Since $\log_b a = \log_2 2 = 1$, we get $f(n) = \Theta(n^{1}) = \Theta(n^{\log_b a})$, which is case 2. Hence $T(n) = \Theta(n\log n)$.

(b) Binary search. For $T(n) = T(n/2) + \Theta(1)$ we have $a = 1$, $b = 2$, $f(n) = \Theta(1)$. Since $\log_2 1 = 0$, we get $n^{\log_b a} = n^{0} = 1$ and $f(n) = \Theta(1) = \Theta(n^{\log_b a})$. Again case 2 applies, so $T(n) = \Theta(n^{0}\log n) = \Theta(\log n)$.

(c) Strassen’s matrix multiplication. For $T(n) = 7\,T(n/2) + \Theta(n^{2})$ we have $a = 7$, $b = 2$, $f(n) = \Theta(n^{2})$. Since $\log_2 7 = 2.8073\ldots$, taking $\varepsilon = 0.5$ gives $n^{\log_2 7 - 0.5} = n^{2.307\ldots}$, and $n^{2} = O(n^{2.307\ldots})$ holds. Thus case 1 applies and $T(n) = \Theta(n^{\log_2 7})$, in particular $T(n) = O(n^{2.808})$ — an order strictly smaller than the $\Theta(n^{3})$ of the naive triple loop.

(d) An instance of case 3. For $T(n) = 2\,T(n/2) + n^{2}$ we have $\log_2 2 = 1$, and with $\varepsilon = 1$ we get $n^{2} = \Omega(n^{1+1})$. The regularity condition holds because $2\,(n/2)^{2} = n^{2}/2 \le c\,n^{2}$ with $c = 1/2 < 1$. Hence $T(n) = \Theta(n^{2})$: the cost of the topmost level of the recursion alone determines the total.

7. The dividing line of polynomial time

All the classes seen so far — $\Theta(n)$, $\Theta(n\log n)$, $\Theta(n^2)$, $\Theta(n^3)$ — share the property of being bounded by a polynomial in $n$, whereas $\Theta(2^n)$ and $\Theta(n!)$ do not. As Example 5.4 showed, this boundary cannot be moved by improving the machine. This motivates the following definition.

Definition 7.1（Polynomial-time algorithm）

An algorithm $A$ runs in polynomial time if there is a constant $k$ with $T_A(n) = O(n^{k})$.

The position that polynomial time is the right definition of “efficient” goes back to Cobham and Edmonds. The definition has the drawback of admitting $n^{100}$, but it is strongly justified on two counts. First, the set of polynomials is closed under addition, multiplication and composition, so combining polynomial-time algorithms as building blocks keeps the result polynomial-time. Second, the distinction does not depend on the details of the computational model: complexity differs only polynomially between the RAM model and Turing machines, so the answer to “is it solvable in polynomial time?” does not change when the model does.

Write $\mathrm{P}$ for the class of decision problems solvable in polynomial time, and $\mathrm{NP}$ for the class of decision problems whose “yes” answers admit a certificate verifiable in polynomial time (Definition 4.1［P≠NP 予想とは何か］). The inclusion $\mathrm{P} \subseteq \mathrm{NP}$ is immediate from the definitions, but whether the reverse inclusion holds has been open since the question was posed in 1971. This is the P vs NP problem, and thousands of problems — including subset sum and the travelling salesman problem — are tied to it in the form “if $\mathrm{P} \ne \mathrm{NP}$, then this problem has no polynomial-time algorithm”. See What is the P vs NP problem for details.

This is where the point of learning complexity notation lies. The $O$ notation is at once a tool for measuring the speed of individual programs and the common language in which one discusses what can and cannot be computed.

8. Exercises

Exercise 8.1Easy

Let $f(n) = 3n^{2} + 5n\log_2 n + 100$. Show that $f \in \Theta(n^{2})$ by exhibiting explicit constants $c$ and $n_0$ as in Definition 3.1.

Solution

Upper bound. For $n \ge 2$ we have $\log_2 n \le n$, so $5n\log_2 n \le 5n^{2}$. Also $100 \le n^{2}$ for $n \ge 10$. Hence for $n \ge 10$,

$$f(n) \le 3n^{2} + 5n^{2} + n^{2} = 9n^{2} ,$$

so $f \in O(n^{2})$ with $c_2 = 9$ and $n_0 = 10$.

Lower bound. Since $5n\log_2 n \ge 0$ for $n \ge 1$ and $100 > 0$, we have $f(n) \ge 3n^{2}$ for every $n \ge 1$. Hence $f \in \Omega(n^{2})$ with $c_1 = 3$ and $n_0 = 1$.

Combining the two, $f \in \Theta(n^{2})$ with $c_1 = 3$, $c_2 = 9$, $n_0 = 10$. Incidentally, the inequality $\log_2 n \le n$ (for $n \ge 1$) is also guaranteed by $\log_2 n \in o(n)$, which follows from the first claim of Theorem 4.2; but here it comes directly from $2^{n} \ge n$ for $n \ge 2$ (by induction on $n$: $2^{2} = 4 \ge 2$, and if $2^{n} \ge n$ then $2^{n+1} = 2\cdot 2^{n} \ge 2n \ge n+1$).

Exercise 8.2Standard

Show that $\log_2(n!) \in \Theta(n\log n)$. Do not use Stirling’s formula.

Solution

Upper bound. Since $n! = \prod_{i=1}^{n} i \le \prod_{i=1}^{n} n = n^{n}$, taking $\log_2$ of both sides (which is increasing) gives

$$\log_2(n!) \le \log_2(n^{n}) = n\log_2 n .$$

Hence $\log_2(n!) \in O(n\log n)$ with $c = 1$ and $n_0 = 1$.

Lower bound. Let $n \ge 2$ and keep only the larger half of the factors. There are at least $n/2$ indices $i$ with $i \ge \lceil n/2\rceil$, and each such factor is at least $n/2$, so

$$n! \ge \prod_{i=\lceil n/2\rceil}^{n} i \ge \left(\frac{n}{2}\right)^{n/2} .$$

Taking $\log_2$,

$$\log_2(n!) \ge \frac{n}{2}\left(\log_2 n - 1\right) .$$

For $n \ge 4$ we have $\log_2 n \ge 2$, so $\log_2 n - 1 \ge \log_2 n - \frac{1}{2}\log_2 n = \frac{1}{2}\log_2 n$. Hence

$$\log_2(n!) \ge \frac{n}{4}\log_2 n \qquad (n \ge 4) ,$$

giving $\log_2(n!) \in \Omega(n\log n)$ with $c = 1/4$ and $n_0 = 4$. Together we obtain $\Theta(n\log n)$.

This estimate is used in proving the $\Omega(n\log n)$ lower bound on the worst-case number of comparisons in comparison sorting (Theorem 6.1［Sorting Algorithms］).

Exercise 8.3Standard

Solve the recurrence $T(1) = 1$, $T(n) = 3\,T(n/4) + n\log_2 n$ (with $n$ a power of $4$). State explicitly which case of Theorem 6.1 applies and whether the regularity condition is satisfied.

Solution

Here $a = 3$, $b = 4$, $f(n) = n\log_2 n$. First compute $\log_b a = \log_4 3 = 0.7924\ldots$.

Which case. Taking $\varepsilon = 0.2$ gives $\log_4 3 + \varepsilon = 0.9924\ldots < 1$. For $n \ge 2$ we have $\log_2 n \ge 1$, so $f(n) = n\log_2 n \ge n \ge n^{0.9925}$, and therefore $f(n) = \Omega(n^{\log_4 3 + \varepsilon})$. Thus the first condition of case 3 is met.

Regularity condition. For $n = 4^{k}$ with $k \ge 1$,

$$a\,f(n/b) = 3\cdot\frac{n}{4}\log_2\frac{n}{4} = \frac{3}{4}\,n\left(\log_2 n - 2\right) \le \frac{3}{4}\,n\log_2 n = \frac{3}{4}\,f(n) .$$

We may take $c = 3/4 < 1$, so the regularity condition holds (the inequality $\log_2 n - 2 \le \log_2 n$ follows from $-2 \le 0$).

Conclusion. By case 3 of Theorem 6.1, $T(n) = \Theta(f(n)) = \Theta(n\log n)$. The branching factor $3$ loses to the shrinking factor $4$, so the cost of the topmost level alone determines the total.

Exercise 8.4Hard

Construct an explicit pair of nonnegative functions $f, g$ with $f \notin O(g)$ and $g \notin O(f)$, and prove it. This example shows that the hypothesis of Proposition 3.3 — the existence of the limit — is essential.

Solution

Construction. Define functions on $\mathbb{N}$ by

$$f(n) = \begin{cases} n^{2} & (n \text{ even}) \\ n & (n \text{ odd}) \end{cases} \qquad g(n) = \begin{cases} n & (n \text{ even}) \\ n^{2} & (n \text{ odd}) \end{cases}$$

Both are nonnegative.

Proof that $f \notin O(g)$. Suppose $f \in O(g)$. Then there are $c > 0$ and $n_0$ such that $f(n) \le c\,g(n)$ for every $n \ge n_0$. Choose an even $n$ with $n \ge \max(n_0, \lceil c \rceil + 1)$ (such an even number exists). For this $n$ we have $f(n) = n^{2}$ and $g(n) = n$, so the inequality reads $n^{2} \le c\,n$, that is $n \le c$. But $n \ge \lceil c\rceil + 1 > c$, a contradiction. Hence $f \notin O(g)$.

Proof that $g \notin O(f)$. Run exactly the same argument with odd numbers in place of even ones. Assuming $g \in O(f)$, take $c, n_0$ and an odd $n \ge \max(n_0, \lceil c\rceil + 1)$; then $g(n) = n^{2}$ and $f(n) = n$, so $n \le c$, a contradiction.

Relation to the limit. The ratio $f(n)/g(n)$ equals $n$ for even $n$ and $1/n$ for odd $n$, so it oscillates as $n \to \infty$ and has no limit. Since Proposition 3.3 assumes the existence of the limit, it does not apply to this example. The lesson of the exercise is that the ordering by $O$ notation is not a total order.

References

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 — Chapter 3 (asymptotic notation) and Chapter 4 (divide and conquer, recurrences, and the floor-function form of the master theorem).
2. D. E. Knuth, “Big Omicron and big Omega and big Theta”, ACM SIGACT News 8 (1976), 18–24. DOI: 10.1145/1008328.1008329 — the paper that systematised the use of $O$, $\Omega$ and $\Theta$ for computer science.
3. D. E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd ed., Addison-Wesley, 1997 — Section 1.2.11 (asymptotic representations).
4. R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994 — Chapter 9 (Asymptotics), with a detailed treatment of the techniques of asymptotic expansion.
5. J. Kleinberg, É. Tardos, Algorithm Design, Addison-Wesley, 2005 — Chapter 2 (the basics of algorithm analysis and the standard complexity classes).
6. M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979 — Chapter 1, which contains a table contrasting polynomial and exponential time against improvements in machine speed.

Appendix: When the master theorem does not apply

Theorem 6.1 was stated for $n$ a power of $b$. Actual recurrences involve floor functions, and the shape of the splitting sometimes falls outside the scope of the master theorem. In such cases the substitution method — guess the answer and verify it by induction — is available. We illustrate it on the exact recurrence for merge sort.

Define $T(1) = 1$ and $T(n) = 2\,T(\lfloor n/2\rfloor) + n$ for $n \ge 2$ (real merge sort splits into $\lfloor n/2 \rfloor$ and $\lceil n/2\rceil$; we use this simplified form in order to exhibit the technique).

Upper bound. We show $T(n) \le 2n\log_2 n$ for all $n \ge 2$ by strong induction on $n$.

• $n = 2$: $T(2) = 2T(1) + 2 = 4$ and $2\cdot 2\log_2 2 = 4$, so $T(2) \le 4$ holds.
• $n = 3$: $T(3) = 2T(1) + 3 = 5$ and $2\cdot 3\log_2 3 = 9.50\ldots$, so the bound holds.
• $n \ge 4$: here $\lfloor n/2\rfloor \ge 2$ and $\lfloor n/2 \rfloor < n$, so the induction hypothesis applies and gives $T(\lfloor n/2\rfloor) \le 2\lfloor n/2\rfloor \log_2 \lfloor n/2\rfloor$. Using $\lfloor n/2\rfloor \le n/2$ and the monotonicity of $\log_2$,

$$T(n) \le 2\cdot 2\cdot\frac{n}{2}\log_2\frac{n}{2} + n = 2n(\log_2 n - 1) + n = 2n\log_2 n - n \le 2n\log_2 n ,$$

the last inequality following from $n > 0$.

Hence $T(n) = O(n\log n)$. The essential point is the leftover $-n$: the induction went through precisely because of that slack. Had we tried to prove $T(n) \le c\,n\log_2 n$ with $c = 1$, the remainder would not have been at most $0$ and the induction would not have closed.

Lower bound. We first show that $T$ is nondecreasing, proving $T(n) \ge T(n-1)$ for $n \ge 2$ by strong induction on $n$. For $n = 2$ we have $T(2) = 4 \ge T(1) = 1$. For $n \ge 3$ we have $\lfloor n/2\rfloor \ge \lfloor (n-1)/2\rfloor \ge 1$, so the induction hypothesis (monotonicity of $T$ at arguments below $n$) gives $T(\lfloor n/2\rfloor) \ge T(\lfloor (n-1)/2\rfloor)$. Hence

$$T(n) = 2T(\lfloor n/2\rfloor) + n \ge 2T(\lfloor (n-1)/2\rfloor) + (n-1) = T(n-1)$$

(for $n = 3$ the right-hand side is precisely the defining recurrence for $T(2)$, and the same holds for $n \ge 4$).

Next we compute the value at $n$ a power of two, $n = 2^{k}$. From $T(2^{k}) = 2T(2^{k-1}) + 2^{k}$ and $T(1) = 1$, induction on $k$ gives $T(2^{k}) = 2^{k}(k+1)$. Indeed, for $k = 0$ we have $2^{0}(0+1) = 1 = T(1)$, and if the formula holds for $k-1$ then

$$T(2^{k}) = 2\cdot 2^{k-1}k + 2^{k} = 2^{k}k + 2^{k} = 2^{k}(k+1) .$$

For general $n \ge 1$ put $m = 2^{\lfloor \log_2 n\rfloor}$, so that $m \le n$ and $m > n/2$. By monotonicity,

$$T(n) \ge T(m) = m\left(\lfloor\log_2 n\rfloor + 1\right) > \frac{n}{2}\log_2 n$$

(using $\lfloor \log_2 n\rfloor + 1 > \log_2 n$). Hence $T(n) = \Omega(n\log n)$, and together with the upper bound, $T(n) = \Theta(n\log n)$.

The key to the substitution method is to fix the exact form to be proved before starting the induction. Assuming only an order such as $O(n\log n)$ and inducting leads to the classic error in which the constant grows at every step and diverges. Write the bound out with its constants, as in $T(n) \le 2n\log_2 n$, and check that the induction step preserves the same constant.