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

> Defines time and space complexity from a machine model, states O, Ω and Θ as sets of functions, proves the growth hierarchy, and compares classes from O(1) to O(2^n) numerically.
> https://rikai.mugen-giken.com/en/computer-science/algorithms/complexity-and-big-o

## 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 id="def-ram" title="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.
</Definition>

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 id="rem-model-caveat">
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.
</Remark>

### 2.2. Time and space complexity

<Definition id="def-complexity" title="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$.
</Definition>

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 id="prop-space-time" title="Space is bounded by time">
Suppose an algorithm $A$ accesses at most $\kappa$ memory cells per basic operation (in the model of <Ref to="def-ram" /> 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))$.
</Proposition>

<Proof of="prop-space-time">
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 <Ref to="def-big-o" /> yields $S_A(n) = O(T_A(n))$.
</Proof>

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 id="ex-insertion-sort" title="Counting the comparisons of insertion sort to the end">
Consider insertion sort, which rearranges an array of length $n$ into increasing order.

```python
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 <Ref to="def-big-o" />).

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

<Remark id="rem-worst-average">
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 <Ref to="ex-insertion-sort" text="insertion sort" /> 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 (<Ref to="computer-science/algorithms/sorting#thm-quicksort-average" />), and in practice it is this average that governs. See [Sorting algorithms](/en/computer-science/algorithms/sorting) for details. Unless stated otherwise, every complexity in this article is worst-case.
</Remark>

## 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 id="def-big-o" title="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$".
</Definition>

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.

<Figure caption="What the definition of O notation asserts">
<Mermaid code={`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)"]`} />
</Figure>

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

<Definition id="def-little-o" title="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$.
</Definition>

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 id="prop-limit-criterion" title="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)$.
</Proposition>

<Proof of="prop-limit-criterion">
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 <Ref to="def-big-o" /> 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, <Ref to="def-little-o" /> 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)$.
</Proof>

When the limit fails to exist the test is unusable. The $O$ notation itself remains meaningful nonetheless (see <Ref to="exr-incomparable" />).

<Proposition id="prop-calculus" title="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)$.
</Proposition>

<Proof of="prop-calculus">
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)$.
</Proof>

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 id="prop-polynomial" title="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)$.
</Proposition>

<Proof of="prop-polynomial">
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)$.
</Proof>

### 3.3. Pitfalls of the notation

<Remark id="rem-equals-abuse">
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>

<Remark id="rem-log-base">
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.
</Remark>

<Aside type="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.
</Aside>

## 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 id="lem-exp-beats-poly" title="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 .
$$
</Lemma>

<Proof of="lem-exp-beats-poly">
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$.
</Proof>

<Theorem id="thm-hierarchy" title="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.
</Theorem>

<Proof of="thm-hierarchy">
**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 <Ref to="lem-exp-beats-poly" /> with $c = 2^{\varepsilon}$, $k = a$ and $x = t$ shows that this ratio tends to $0$. By part 3 of <Ref to="prop-limit-criterion" />, $(\log_2 n)^a \in o(n^{\varepsilon})$.

**Second claim.** Applying <Ref to="lem-exp-beats-poly" /> directly with $x = n$ gives $n^k/c^n \to 0$, and again part 3 of <Ref to="prop-limit-criterion" /> 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!)$.
</Proof>

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.

<Figure caption="Representative growth rates (the vertical axis is truncated at 100)">
<svg viewBox="0 0 660 400" width="100%" role="img" aria-label="Comparison of the growth of log n, n, n log n, n^2 and 2^n">
  <g stroke="currentColor" stroke-width="1" opacity="0.18">
    <line x1="70" y1="265" x2="600" y2="265" />
    <line x1="70" y1="190" x2="600" y2="190" />
    <line x1="70" y1="115" x2="600" y2="115" />
    <line x1="70" y1="40" x2="600" y2="40" />
  </g>
  <g stroke="currentColor" stroke-width="1.5" fill="none">
    <line x1="70" y1="340" x2="600" y2="340" />
    <line x1="70" y1="340" x2="70" y2="35" />
  </g>
  <g stroke="currentColor" stroke-width="1" fill="none" opacity="0.7">
    <line x1="189.7" y1="340" x2="189.7" y2="345" />
    <line x1="326.5" y1="340" x2="326.5" y2="345" />
    <line x1="463.2" y1="340" x2="463.2" y2="345" />
    <line x1="600" y1="340" x2="600" y2="345" />
  </g>
  <g fill="currentColor" font-size="12" opacity="0.8">
    <text x="70" y="358" text-anchor="middle">1</text>
    <text x="189.7" y="358" text-anchor="middle">8</text>
    <text x="326.5" y="358" text-anchor="middle">16</text>
    <text x="463.2" y="358" text-anchor="middle">24</text>
    <text x="600" y="358" text-anchor="middle">32</text>
    <text x="62" y="344" text-anchor="end">0</text>
    <text x="62" y="269" text-anchor="end">25</text>
    <text x="62" y="194" text-anchor="end">50</text>
    <text x="62" y="119" text-anchor="end">75</text>
    <text x="62" y="44" text-anchor="end">100</text>
  </g>
  <polyline fill="none" stroke="currentColor" stroke-width="2" stroke-dasharray="2 4"
    points="70,340 87.1,337.0 104.2,335.2 121.3,334.0 155.5,332.2 189.7,331.0 258.1,329.2 326.5,328.0 463.2,326.2 600,325.0" />
  <polyline fill="none" stroke="currentColor" stroke-width="2" stroke-dasharray="8 4"
    points="70,337 600,244" />
  <polyline fill="none" stroke="var(--sl-color-accent)" stroke-width="3"
    points="70,340 87.1,334.0 104.2,325.7 121.3,316.0 138.4,305.2 155.5,293.5 189.7,268.0 223.9,240.3 258.1,210.9 292.3,180.1 326.5,148.0 360.6,114.8 394.8,80.7 429.0,45.7 435.9,40" />
  <polyline fill="none" stroke="currentColor" stroke-width="2"
    points="70,337 87.1,328 104.2,313 121.3,292 138.4,265 155.5,232 172.6,193 189.7,148 206.8,97 223.9,40" />
  <polyline fill="none" stroke="currentColor" stroke-width="2" stroke-dasharray="1 3"
    points="70,334 87.1,328 104.2,316 121.3,292 138.4,244 146.9,204.2 155.5,148 160.6,103.6 166.5,40" />
  <g fill="currentColor" font-size="13">
    <text x="155" y="32" text-anchor="end">2ⁿ</text>
    <text x="230" y="32" text-anchor="start">n²</text>
    <text x="442" y="32" text-anchor="start" fill="var(--sl-color-accent)">n log n</text>
    <text x="606" y="248" text-anchor="start">n</text>
    <text x="606" y="329" text-anchor="start">log n</text>
  </g>
  <g fill="currentColor" font-size="13" opacity="0.9">
    <text x="335" y="380" text-anchor="middle">n (input size)</text>
    <text x="20" y="190" text-anchor="middle" transform="rotate(-90 20 190)">number of basic operations</text>
  </g>
</svg>
</Figure>

## 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 id="prop-doubling" title="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}$.
</Proposition>

<Proof of="prop-doubling">
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}$.
</Proof>

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 id="rem-theta-ratio">
<Ref to="prop-doubling" /> 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.
</Remark>

### 5.2. The numbers

<Example id="ex-growth-numbers" title="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 <Ref to="computer-science/algorithms/searching#thm-binary-cost" /> and [Search algorithms](/computer-science/algorithms/searching)).

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.
</Example>

### 5.3. A faster machine will not save us

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

<Example id="ex-faster-machine" title="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>

<Example id="ex-subset-sum" title="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 <Ref to="computer-science/algorithms/dynamic-programming#cor-knapsack-time" />; see [Dynamic programming](/computer-science/algorithms/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**.
</Example>

### 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 (<Ref to="computer-science/algorithms/data-structures#prop-list" />). 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](/en/computer-science/algorithms/data-structures).

<Remark id="rem-amortized">
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 <Ref to="computer-science/algorithms/data-structures#thm-dynamic-array" />). It is a different notion from the worst-case complexity of an individual operation, and the two should be kept apart.
</Remark>

## 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)$ (<Ref to="computer-science/algorithms/sorting#thm-mergesort" />). Recurrences of this shape are solved at a stroke by the following theorem.

<Theorem id="thm-master" title="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))$.
</Theorem>

<Proof of="thm-master">
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 (<Ref to="rem-log-base" />), $\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))$.
</Proof>

<Remark id="rem-master-general">
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 <Ref to="thm-master" /> 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.
</Remark>

<Example id="ex-master-apply" title="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.
</Example>

## 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 <Ref to="ex-faster-machine" /> showed, this boundary cannot be moved by improving the machine. This motivates the following definition.

<Definition id="def-poly-time" title="Polynomial-time algorithm">
An algorithm $A$ runs in **polynomial time** if there is a constant $k$ with $T_A(n) = O(n^{k})$.
</Definition>

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 (<Ref to="computer-science/algorithms/p-vs-np#def-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](/computer-science/algorithms/p-vs-np) 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 id="exr-theta-poly" difficulty="Easy">
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 <Ref to="def-big-o" />.
<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 <Ref to="thm-hierarchy" />; 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$).
</Solution>
</Exercise>

<Exercise id="exr-log-factorial" difficulty="Standard">
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 (<Ref to="computer-science/algorithms/sorting#thm-comparison-lower-bound" />).
</Solution>
</Exercise>

<Exercise id="exr-recurrence" difficulty="Standard">
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 <Ref to="thm-master" /> 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 <Ref to="thm-master" />, $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.
</Solution>
</Exercise>

<Exercise id="exr-incomparable" difficulty="Hard">
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 <Ref to="prop-limit-criterion" /> — 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 <Ref to="prop-limit-criterion" /> 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.
</Solution>
</Exercise>

## 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](https://doi.org/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

<Ref to="thm-master" /> 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.