1 — Complexity analysis

Complexity analysis predicts how the cost of an algorithm grows with the size of its input. The essay Big-O complexity covers the everyday version: what O(n) means, the common complexity classes with timings, how to read a loop nest, and the usual ways to make code faster. This chapter assumes that material and goes underneath it. It gives the exact definitions with their constants, separates the different kinds of “case” that get blurred together, works through amortized analysis three ways on a real dynamic array, solves divide-and-conquer recurrences with the Master Theorem and with Akra–Bazzi where the Master Theorem does not apply, and measures where the model breaks down on real hardware.

Timings in this chapter were measured with Python 3.14 on one Mac (an Apple M3 Pro). Exact numbers will differ on other machines and versions. The ratios and the shapes of the curves are what carry over.

The cost model

Every complexity statement is relative to a model of what one “step” costs. The standard one is the word RAM model:

• Memory is an array of words, and reading or writing any word costs one step regardless of its address.
• Arithmetic, comparison and branching on a single word cost one step.
• A word holds about $\log n$ bits, enough to store an index into the input.

Under this model, a[i] is O(1), adding two machine integers is O(1), and comparing two keys is O(1). Each of these assumptions can fail in practice, and later sections show where:

• Python integers are arbitrary precision, so multiplying two 100,000-digit numbers is not one step.
• Comparing two strings costs time proportional to their common prefix.
• Memory access is not uniform. A read that hits the L1 cache and one that goes to DRAM differ by roughly two orders of magnitude.

When comparison is the expensive operation, as in sorting and searching, algorithms are often analyzed by counting comparisons instead of all steps. That is the model behind the n log n lower bound for sorting in chapter 3.

Asymptotic notation, precisely

All five symbols describe sets of functions. Writing $f(n) = O(g(n))$ is a convention for $f \in O(g)$, and the equals sign only reads left to right: $n = O(n^2)$ is true, and $O(n^2) = n$ means nothing.

For functions that are non-negative for large $n$:

The difference between big-O and little-o is the quantifier on $c$. Big-O needs one constant that works; little-o needs every constant to work eventually. So $2n = O(n)$ but $2n \ne o(n)$, while $n = o(n \log n)$.

$f = \Theta(g)$ holds exactly when both $f = O(g)$ and $f = \Omega(g)$.

Finding the constants

Take $f(n) = 3n^2 + 10n + 5$. The claim is $f = \Theta(n^2)$.

Upper bound. Pick $c_2 = 4$. Then $3n^2 + 10n + 5 \le 4n^2$ is the same as $10n + 5 \le n^2$. At $n = 10$ the left side is 105 and the right is 100, so it fails. At $n = 11$ it is 115 against 121, and for larger $n$ the gap only widens. So $c_2 = 4, n_0 = 11$ works.

Lower bound. Pick $c_1 = 3$. Then $3n^2 \le 3n^2 + 10n + 5$ for every $n \ge 0$, so $n_0 = 0$ works for this side.

Both hold for $n \ge 11$, so $f = \Theta(n^2)$ with $c_1 = 3, c_2 = 4, n_0 = 11$. The constants are not unique. $c_2 = 18$ and $n_0 = 1$ also works, because $3n^2 + 10n + 5 \le 3n^2 + 10n^2 + 5n^2$ for $n \ge 1$. Any valid pair proves the claim.

Showing a bound fails. To show $n^2 \ne O(n)$, suppose $n^2 \le cn$ for all $n \ge n_0$. Dividing by $n$ gives $n \le c$ for all large $n$, which is false for $n > c$. No constant can work.

The limit test

When $\lim_{n \to \infty} f(n)/g(n)$ exists, it settles the relationship directly:

For example, $\lim (\log n)/n^{0.01} = 0$ by L’Hôpital’s rule, so any power of $n$, however small, eventually beats a logarithm. The limit need not exist. For $f(n) = n^{1 + \sin n}$ and $g(n) = n$ the ratio oscillates between about $1/n$ and $n$, so neither $f = O(g)$ nor $f = \Omega(g)$ holds. Asymptotic notation does not impose a total order on functions.

Useful facts

• Logarithm bases do not matter inside O. $\log_a n = \log_b n / \log_b a$, which differs by a constant factor. Writing O(log n) without a base is correct.
• Exponential bases do matter. $3^n / 2^n = 1.5^n \to \infty$, so $3^n \ne O(2^n)$. Likewise $2^{2n} = 4^n$ is not $O(2^n)$.
• Sums take the maximum. $O(f) + O(g) = O(\max(f, g))$.
• Products multiply. $O(f) \cdot O(g) = O(f g)$.
• Polynomials. A degree-$d$ polynomial with positive leading coefficient is $\Theta(n^d)$.
• Factorials. $\log(n!) = \Theta(n \log n)$. From Stirling’s approximation, $\log_2 n! = n \log_2 n - n \log_2 e + O(\log n)$. This is the number behind the sorting lower bound.
• Harmonic numbers. $1 + 1/2 + \dots + 1/n = \ln n + O(1)$. It appears in the analysis of quicksort, hashing and the coupon collector problem.

The usual hierarchy, each strictly slower than the next:

$1 \;<\; \log \log n \;<\; \log n \;<\; \sqrt{n} \;<\; n \;<\; n \log n \;<\; n^2 \;<\; n^3 \;<\; 2^n \;<\; n! \;<\; n^n$

Several variables

Inputs with more than one size need more than one variable. A graph algorithm is O(V + E), a string search is O(n + m), a matrix product is O(n m p). Collapsing these to O(n) loses information: O(V + E) on a dense graph is $O(V^2)$, and on a sparse one it is O(V). The definitions extend by requiring the inequality once every variable is past its threshold.

Common misstatements

“Big-O means worst case.” It does not. O, Ω and Θ are bounds on a function. The function can be the worst-case running time, the best-case running time, the average, or the memory use. “Quicksort’s worst case is $\Theta(n^2)$” and “quicksort’s best case is $\Theta(n \log n)$” are both precise statements. What people usually mean by “the complexity of X is O(f)” is “the worst-case running time of X is O(f)”.

“O(n) means it takes about n steps.” O(n) is only an upper bound. A function that always runs in constant time is also O(n), and O(n²), and O(2ⁿ). When the bound is tight, Θ is the accurate symbol. Most everyday use of O means Θ.

“O(1) means fast.” It means bounded by a constant. A hash lookup that computes SHA-256 over a 1 MB key is O(1) in the number of stored keys.

“An O(n log n) algorithm beats an O(n²) one.” Only past some input size, and the crossover can be large. Insertion sort beats merge sort on small arrays, which is why production sorts switch to it for short ranges.

Best, worst, average, expected and amortized

These five terms describe different quantities. Mixing them up is the most frequent source of wrong complexity claims.

Worst and best case

Insertion sort shows all three input cases cleanly. It inserts each element into the sorted prefix to its left, scanning backward until it finds a smaller element. Counting comparisons on 1,000 elements:

n = 1000
sorted input:        999 comparisons   (n - 1 = 999)
random input:    250,253 comparisons   (about n^2/4 = 250,000)
reversed input:  499,500 comparisons   (n(n-1)/2 = 499,500)

On sorted input each new element stops after one comparison, giving $n - 1$. On reversed input each element walks the whole prefix, giving $\sum_{i=1}^{n-1} i = n(n-1)/2$. So insertion sort is $\Theta(n)$ in the best case and $\Theta(n^2)$ in the worst.

The best case is rarely useful as a guarantee, because an adversary or an unlucky input never has to supply it. It is useful when real inputs are known to be close to it: insertion sort’s linear best case is why it works well on nearly sorted data.

Average case

The random-input row above is an average-case result. Each pair of elements that is out of order (an inversion) costs one shift. A uniformly random permutation of $n$ elements has $n(n-1)/4$ inversions on average, because each of the $\binom{n}{2}$ pairs is inverted with probability 1/2. That is where $n^2/4$ comes from, and 250,253 is within 0.1% of it.

An average-case result is only as good as its distribution. Insertion sort’s average is $\Theta(n^2)$ on random permutations, but if real inputs are logs with occasional late arrivals, the number of inversions is small and the real cost is close to linear.

Linear search for a key that is present, at a uniformly random position, makes $(n + 1)/2$ comparisons on average. If the key is absent, every search makes $n$. The “average case” depends on what fraction of searches miss, which the algorithm has no control over.

Expected time of a randomized algorithm

Quicksort with a pivot chosen uniformly at random has expected running time $O(n \log n)$ on every input, including sorted and reversed ones. The expectation is over the coin flips the algorithm makes, not over inputs. No input is bad; only unlucky coin flips are, and the probability of $\Theta(n^2)$ behavior is vanishingly small for large $n$.

This is a stronger guarantee than an average-case bound. Deterministic quicksort with the first element as pivot has $O(n \log n)$ average-case time over random permutations, but sorted input, which is common, triggers its $\Theta(n^2)$ worst case every time.

Amortized time

Amortized analysis bounds the total cost of any sequence of $m$ operations, in the worst case, and divides by $m$. Nothing is random, and no distribution is assumed. “Appending to a Python list is amortized O(1)” means any sequence of $m$ appends costs O(m) in total, even though a single append can cost O(n). It is covered in detail below.

Smoothed analysis

A fifth notion sits between worst and average. Smoothed analysis, introduced by Daniel Spielman and Shang-Hua Teng in 2001, takes the worst input and then adds small random noise to it, and measures the expected cost of the perturbed input. It explains why the simplex method for linear programming, which has exponential worst-case examples, runs in polynomial time in practice: its bad inputs are fragile, and a small perturbation destroys them.

Space complexity

Space complexity measures the memory an algorithm uses as a function of input size. Two conventions are in use:

• Total space counts the input as well.
• Auxiliary space counts only the extra memory beyond the input.

“Merge sort uses O(n) space” refers to auxiliary space; its total space is also O(n), so the distinction looks pointless there. It matters for algorithms like binary search, whose total space is O(n) because of the array, but whose auxiliary space is O(1). Algorithm descriptions almost always mean auxiliary space, and in-place means O(1) auxiliary space, or sometimes O(log n) to allow a recursion stack.

Output is usually excluded too. An algorithm that returns all subsets of a set must use $\Theta(n 2^n)$ memory to hold its output, which says nothing about the algorithm.

Measured: a list against a generator

These two functions compute the same sum and have the same time complexity:

def squares_list(n):
    return sum([i * i for i in range(n)])

def squares_gen(n):
    return sum(i * i for i in range(n))

Peak memory allocated during each call, measured with tracemalloc:

squares_list  n=   10,000  peak     394.4 KiB
squares_list  n=  100,000  peak    3903.7 KiB
squares_list  n=1,000,000  peak   39497.1 KiB
squares_gen   n=   10,000  peak       0.4 KiB
squares_gen   n=  100,000  peak       0.4 KiB
squares_gen   n=1,000,000  peak       0.4 KiB

The list version is O(n) auxiliary space, about 40 bytes per element: an 8-byte pointer in the list plus a 28-byte integer object, rounded up by the allocator. The generator version is O(1). This difference often decides whether a job fits in memory.

The recursion stack

Every active function call holds a stack frame with its arguments, local variables and return address. A recursive algorithm’s space includes the deepest chain of simultaneous calls, even when it allocates no data structure.

def total(xs, i=0):
    if i == len(xs):
        return 0
    return xs[i] + total(xs, i + 1)

This function uses O(1) memory per call and recurses $n$ deep, so its auxiliary space is $\Theta(n)$. CPython caps Python-level recursion depth:

1000
404550
RecursionError: maximum recursion depth exceeded

The first line is sys.getrecursionlimit(). Summing 900 elements works; summing 5,000 raises RecursionError. CPython does not eliminate tail calls, so rewriting the function in tail-recursive form does not help. The fix is a loop.

The stack depth of the common recursive algorithms:

The quicksort row is a standard technique: after partitioning, recurse into the smaller part and handle the larger part by updating the loop bounds. Since the recursive call always gets at most half the elements, the depth is at most $\log_2 n$ regardless of pivot quality. Chapter 3 uses it.

Time and space trade off

Many speedups spend memory: a hash set to make membership O(1), a memo table to avoid recomputation, a prefix-sum array to answer range queries in O(1). Some go the other way: recomputing a value instead of storing it, or streaming data instead of loading it. When memory is the binding constraint, the right question is often “what is the least I need to keep?”, and the answer leads to streaming algorithms, reservoir sampling (chapter 17) and the two-pointer and sliding-window techniques of chapter 4.

Amortized analysis

Some data structures do a little work on most operations and a lot of work on a few. Amortized analysis shows that the expensive operations are rare enough that the average over any sequence is small. The guarantee is about sequences, in the worst case: no input can make the total exceed the bound.

The standard example is the dynamic array, the structure behind Python’s list, C++‘s std::vector and Java’s ArrayList. It stores elements in a fixed-size block. When the block is full, appending allocates a larger block, copies every element across, and frees the old one.

A dynamic array with a growth policy

class DynamicArray:
    def __init__(self, grow):
        self._grow = grow          # function: old capacity -> new capacity
        self._cap = 1
        self._n = 0
        self._data = [None]
        self.copies = 0            # element copies done by resizing

    def append(self, x):
        if self._n == self._cap:
            new_cap = self._grow(self._cap)
            new = [None] * new_cap
            for i in range(self._n):       # the expensive part
                new[i] = self._data[i]
            self.copies += self._n
            self._data, self._cap = new, new_cap
        self._data[self._n] = x
        self._n += 1

An append when the array is full costs $\Theta(n)$. Everything depends on how often that happens, which depends on the growth policy. Three policies, measured:

With either multiplicative policy, copies per append stay flat as $n$ grows, and total time grows linearly. With additive growth, copies per append grow linearly with $n$, so total time is quadratic: four times the appends took about 16 times as long. The three methods below explain both results.

The aggregate method

Sum the actual cost of the whole sequence and divide.

With doubling from capacity 1, resizes happen when the size reaches 1, 2, 4, 8, and so on, copying that many elements. Over $n$ appends the copying costs

$1 + 2 + 4 + \dots + 2^{\lfloor \log_2 (n-1) \rfloor} < 2n$

and the writes cost $n$, so the total is under $3n$ and the amortized cost per append is O(1). The measured 131,071 copies for 100,000 appends is $2^{17} - 1$, the sum of the powers of two up to 65,536.

With growth factor $r > 1$ the copies form a geometric series whose sum is about $n/(r - 1)$ to $rn/(r-1)$, depending on where $n$ falls between resizes. For $r = 2$ that is between 1 and 2 copies per element, matching the measured 1.31. For $r = 1.125$ it is between 8 and 9, matching 8.46 to 8.96. Any constant factor above 1 gives O(1) amortized appends. Smaller factors waste less memory and copy more.

With additive growth of $k$, resizes happen at sizes $k, 2k, 3k, \dots$ and copy that many elements:

$k + 2k + 3k + \dots + \lfloor n/k \rfloor k \approx \frac{n^2}{2k}$

That is $\Theta(n^2)$ total, $\Theta(n)$ amortized per append. For $n = 400{,}000$ and $k = 1{,}000$ the formula gives 80,000,000, and the measurement was 79,800,400. A larger $k$ only moves the constant.

The accounting method

Charge each operation a fixed amortized cost, possibly more than its actual cost. The surplus is stored as credit on specific elements and spent later on expensive operations. If the credit never goes negative, the total charged is an upper bound on the total actual cost.

For doubling, charge 3 units per append:

• 1 unit pays for writing the new element.
• 1 unit is stored on the new element, to pay for copying it at the next resize.
• 1 unit is stored on an element in the older half of the array, which has already spent its own credit on a previous copy.

Just after a resize to capacity $2k$, the array holds $k$ elements and no credit. The next $k$ appends each deposit 2 units, so when the array is full again it holds $2k$ units of credit, exactly enough to copy all $2k$ elements. Credit never goes negative, so $m$ appends cost at most $3m$.

capacity 8, after resize from 4:   [a b c d . . . .]   credit 0
4 more appends, 2 credit each:      [a b c d e f g h]   credit 8
resize to 16, copy 8 elements:      [a b c d e f g h . . . . . . . .]   credit 0

The potential method

Define a potential function $\Phi$ on the state of the structure, with $\Phi \ge 0$ always and $\Phi = 0$ at the start. The amortized cost of an operation is its actual cost plus the change in potential:

$\hat{c}_i = c_i + \Phi_i - \Phi_{i-1}$

Summing over a sequence, the potential terms telescope:

$\sum_{i=1}^m \hat{c}_i = \sum_{i=1}^m c_i + \Phi_m - \Phi_0 \ge \sum_{i=1}^m c_i$

so the total amortized cost bounds the total actual cost. Potential plays the role of stored credit, but it is a function of the state rather than an assignment of coins to elements, which makes it easier to apply to complicated structures.

For a doubling array with size $s$ and capacity $k$, take $\Phi = 2s - k$. Right after a resize the array is just over half full and $\Phi$ is about 2; just before the next one, $s = k$ and $\Phi = k$. If the array starts empty with capacity 0 and the first append allocates one slot, then $\Phi_0 = 0$, and because the array is at least half full from then on, $\Phi \ge 0$ throughout.

• Append without resize. Actual cost 1. $s$ rises by 1, so $\Phi$ rises by 2. Amortized cost $1 + 2 = 3$.
• Append with resize. Before: $s = k$, $\Phi = k$. The append copies $k$ elements and writes one, actual cost $k + 1$. After: $s = k + 1$, capacity $2k$, $\Phi = 2(k+1) - 2k = 2$. Amortized cost $(k + 1) + (2 - k) = 3$.

Both cases cost 3, so any sequence of $m$ appends costs at most $3m$.

What CPython actually does

CPython’s list resizing code in Objects/listobject.c computes the new capacity as

new_allocated = (newsize + (newsize >> 3) + 6) & ~3

that is, the requested size plus one eighth plus 6, rounded down to a multiple of 4. The capacities can be observed through sys.getsizeof, which reports 8 more bytes for each additional slot:

len at resize -> new capacity
   1 -> 4
   5 -> 8
   9 -> 16
  17 -> 24
  25 -> 32
  33 -> 40
  41 -> 52
  53 -> 64
  65 -> 76
  77 -> 92
  93 -> 108
 109 -> 128
 129 -> 148
 149 -> 172
 173 -> 200

For small lists the ”+ 6” dominates, so growth looks like doubling. For large lists the factor approaches 1.125. The comment in the source explains the choice: the growth is mild, but enough to give linear-time amortized behavior over a long sequence of appends.

Appending to a real list, the per-append cost is flat as the list grows by a factor of 1,000, which is what amortized O(1) predicts:

n=     10,000  total     0.11 ms  per append  10.6 ns
n=    100,000  total     1.09 ms  per append  10.9 ns
n=  1,000,000  total    12.77 ms  per append  12.8 ns
n= 10,000,000  total   148.98 ms  per append  14.9 ns

The slight rise at 10 million is the memory hierarchy, covered in the last section, not the algorithm.

The copy is often not a copy. The analysis above charges $\Theta(n)$ for each resize, but CPython grows the block with realloc, and the allocator can frequently extend a block in place or remap pages without moving the data. Timing each of 2,000,000 appends individually, the 92 appends that triggered a resize had a median latency of 417 ns against 83 ns for ordinary appends (both figures include the cost of reading the timer). Resizing a list of over a million elements, which in theory moves 8 MB of pointers, typically took 5 to 10 µs. The single slowest append in the run was a resize at about 257,000 elements, at 139 µs, but the next nine slowest were ordinary appends that resized nothing; those most likely came from the memory allocator and the operating system supplying fresh pages for new integer objects. The amortized bound is a ceiling, and real resizes often come in well under it, while other sources of latency that Big-O does not model can be just as large.

Shrinking without thrashing

Removing elements raises a trap. If the array halves its capacity whenever it becomes half full, then at the boundary an alternating sequence of append, pop, append, pop triggers a grow and a shrink on every operation, each costing $\Theta(n)$. The fix is hysteresis: grow when full, but shrink only when the array falls to a quarter full. After any resize the array is half full, so at least $k/4$ operations must happen before the next one, and the cost is again amortized O(1). CPython’s list shrinks only when the size falls below half the allocation (and, in 3.14, not at all for very small lists), and then reallocates with the same one-eighth slack, which leaves room in both directions.

When amortized is not enough

An amortized bound says nothing about the latency of a single operation. A system that must answer every request within a deadline, such as an audio callback, a trading engine or a garbage collector pause budget, cannot afford an occasional $\Theta(n)$ step even if the average is excellent. The remedy is deamortization: spreading the expensive work across many cheap operations. A deamortized dynamic array allocates the new block early and copies two old elements on each subsequent append, so it is finished by the time the old block is full. Redis resizes its hash tables this way, moving a few buckets on each command rather than rehashing everything at once (Redis internals).

Other classic amortized results

Recurrence relations

A recursive algorithm’s running time is naturally described by a recurrence: the cost on input size $n$ in terms of the cost on smaller sizes. Writing it down is mechanical: count the recursive calls and their sizes, and add the non-recursive work.

Base cases are usually $T(1) = O(1)$ and are left implicit. Floors and ceilings in $n/2$ rarely change the asymptotic answer and are normally dropped.

There are three ways to solve a recurrence.

The recursion tree

Draw the calls as a tree, write the non-recursive work at each node, sum each level, then sum the levels. For merge sort, $T(n) = 2T(n/2) + cn$:

level 0:                 cn                         = cn
level 1:         cn/2          cn/2                 = cn
level 2:     cn/4  cn/4    cn/4  cn/4               = cn
  ...
level k:   2^k nodes, each c n / 2^k                = cn
  ...
leaves:    n nodes of size 1                        = cn

There are $\log_2 n + 1$ levels, each costing $cn$, so $T(n) = \Theta(n \log n)$.

For $T(n) = T(n-1) + cn$ the tree is a path. Level $i$ costs $c(n - i)$, and the total is $c(n + (n-1) + \dots + 1) = \Theta(n^2)$. This is quicksort’s worst case, when every partition peels off one element.

For $T(n) = 2T(n-1) + c$ the tree is complete binary with depth $n$, so it has $2^n - 1$ nodes and $T(n) = \Theta(2^n)$. Towers of Hanoi has exactly this recurrence, and the minimal number of moves is $2^n - 1$.

The substitution method

Guess the answer and prove it by induction. To show $T(n) = 2T(n/2) + n$ is $O(n \log n)$, assume $T(m) \le c\, m \log_2 m$ for all $m < n$. Then

$T(n) \le 2c \tfrac{n}{2} \log_2 \tfrac{n}{2} + n = cn \log_2 n - cn + n \le cn \log_2 n$

for any $c \ge 1$. The induction must prove the exact form of the hypothesis. Proving $T(n) \le cn$ for $T(n) = 2T(n/2) + n$ “works” only if one writes $2c(n/2) + n = O(n)$, which hides a constant that grows at each level; the correct calculation gives $cn + n$, which is not $\le cn$.

The Master Theorem

Most divide-and-conquer recurrences have the form

$T(n) = a\,T(n/b) + f(n)$

with $a \ge 1$ subproblems, each of size $n/b$ for a constant $b > 1$, and $f(n)$ work outside the recursive calls. The Master Theorem solves them by comparing $f(n)$ to $n^{\log_b a}$, which is the number of leaves in the recursion tree: the tree has depth $\log_b n$ and branching factor $a$, so it has $a^{\log_b n} = n^{\log_b a}$ leaves. Call this the watershed function.

The version in the fourth edition of Cormen, Leiserson, Rivest and Stein states three cases:

The intuition is a geometric series over the levels of the recursion tree. Level $j$ has $a^j$ nodes each doing $f(n/b^j)$ work. In case 1 the per-level cost grows geometrically toward the leaves, so the leaves’ $n^{\log_b a}$ dominates. In case 3 it shrinks geometrically away from the root, so the root’s $f(n)$ dominates. In case 2 it is roughly constant across $\log_b n$ levels, which multiplies by one more log factor.

The extra condition in case 3, $a f(n/b) \le c f(n)$, is the regularity condition. It says the work actually shrinks from one level to the next. It holds automatically for polynomials such as $f(n) = n^2$, but can fail for oscillating functions.

Note the $\epsilon$: case 1 and case 3 need $f$ to be smaller or larger than the watershed by a polynomial factor, not just any factor. That leaves gaps, discussed below.

Worked examples

The theorem’s predictions can be checked by evaluating a recurrence exactly. With $T(1) = 1$ and $n$ a power of 2, the ratio $T(n)/g(n)$ should settle to a constant when $g$ is the predicted solution:

8T(n/2) + n^2  -> n^3      (case 1)
   n=2^10: T(n)/g(n) = 1.9990
   n=2^15: T(n)/g(n) = 2.0000
   n=2^20: T(n)/g(n) = 2.0000
2T(n/2) + n    -> n log n  (case 2)
   n=2^10: T(n)/g(n) = 1.1000
   n=2^15: T(n)/g(n) = 1.0667
   n=2^20: T(n)/g(n) = 1.0500
2T(n/2) + n^2  -> n^2      (case 3)
   n=2^10: T(n)/g(n) = 1.9990
   n=2^15: T(n)/g(n) = 2.0000
   n=2^20: T(n)/g(n) = 2.0000

Case 2 converges slowly because the exact solution is $n \log_2 n + n$, and the $+n$ term shrinks relative to $n \log_2 n$ only logarithmically.

Measured: Karatsuba in CPython

CPython multiplies large integers with Karatsuba’s algorithm, which splits each number in half and replaces four half-size products with three. The recurrence is $T(n) = 3T(n/2) + O(n)$, which is case 1 with solution $\Theta(n^{\log_2 3})$. Doubling the number of bits should multiply the time by $2^{1.585} = 3$:

      bits      x * y  ratio
    20,000    160.7 µs 
    40,000    492.8 µs   3.07
    80,000   1480.5 µs   3.00
   160,000   4449.5 µs   3.01
   320,000  13402.1 µs   3.01
   640,000  40320.5 µs   3.01

The ratio is 3.00 to two decimal places. Schoolbook multiplication would give 4. This is also a reminder that the word RAM’s “arithmetic is O(1)” applies only to numbers that fit in a machine word.

Where the Master Theorem does not apply

The theorem needs equal-sized subproblems, a constant number of them, a constant shrink factor, and an $f(n)$ that is polynomially separated from the watershed or matches it up to a log power. Common recurrences that fail one of these:

Subtract-and-conquer. $T(n) = T(n-1) + n$ shrinks by subtraction, not division. Use the recursion tree: $\Theta(n^2)$. Likewise $T(n) = 2T(n-1) + 1$ is $\Theta(2^n)$. There is a separate “master theorem for decreasing functions” for $T(n) = aT(n-b) + f(n)$, but unrolling is usually quicker.

The gap between cases 1 and 2. $T(n) = 2T(n/2) + n/\log n$ has watershed $n$, and $n / \log n$ is smaller than $n$ but not by a polynomial factor, so case 1 does not apply; and it is not $\Theta(n \log^k n)$ for any $k \ge 0$, so case 2 does not either. The recursion tree solves it. Level $j$ has $2^j$ nodes of size $n/2^j$, each costing $(n/2^j)/\log_2(n/2^j)$, so the level costs $n/(\log_2 n - j)$. Summing $j$ from 0 to $\log_2 n - 1$ gives $n(1 + 1/2 + \dots + 1/\log_2 n) = n H_{\log_2 n}$, which is $\Theta(n \log \log n)$.

A non-constant number of subproblems. $T(n) = \sqrt{n}\,T(\sqrt{n}) + n$ (van Emde Boas trees have recurrences of this kind) has neither constant $a$ nor constant $b$. Substituting $S(m) = T(2^m)/2^m$ turns it into $S(m) = S(m/2) + 1$, so $S(m) = \Theta(\log m)$ and $T(n) = \Theta(n \log \log n)$.

Unequal splits. $T(n) = T(n/3) + T(2n/3) + n$ has two subproblems of different sizes. The recursion tree gives $\Theta(n \log n)$: each full level costs $n$, and the tree is between $\log_3 n$ and $\log_{3/2} n$ deep. For the general case there is the Akra–Bazzi method.

The Akra–Bazzi method

Mohamad Akra and Louay Bazzi published a generalization in 1998 that handles recurrences of the form

$T(n) = \sum_{i=1}^{k} a_i\, T(b_i n) + g(n)$

with constants $a_i > 0$ and $0 < b_i < 1$, and $g$ of polynomial growth. Find the unique real $p$ with

$\sum_{i=1}^{k} a_i b_i^{\,p} = 1$

Then

$T(n) = \Theta\!\left(n^p \left(1 + \int_1^n \frac{g(u)}{u^{p+1}}\, du\right)\right)$

Small perturbations such as floors, ceilings and $+O(n/\log^2 n)$ in the subproblem sizes do not change the result.

Two examples:

• $T(n) = T(n/3) + T(2n/3) + n$. Solve $(1/3)^p + (2/3)^p = 1$: $p = 1$. The integral is $\int_1^n u/u^2\,du = \ln n$, so $T(n) = \Theta(n \log n)$.
• $T(n) = T(n/5) + T(7n/10) + n$, the recurrence of the median-of-medians selection algorithm. Here $(1/5)^p + (7/10)^p = 1$ gives $p \approx 0.84$, which is less than 1. The integral is $\int_1^n u^{-p}\,du = \Theta(n^{1-p})$, so $T(n) = \Theta(n^p \cdot n^{1-p}) = \Theta(n)$. The algorithm is linear because the subproblem fractions sum to $1/5 + 7/10 = 9/10 < 1$. Chapter 3 explains where those fractions come from.

The second example generalizes into a rule worth remembering: if $T(n) = \sum T(b_i n) + \Theta(n)$ and $\sum b_i < 1$, then $T(n) = \Theta(n)$. If $\sum b_i = 1$, then $T(n) = \Theta(n \log n)$.

Where Big-O is incomplete

Asymptotic analysis deliberately discards constant factors and assumes uniform memory cost. On real machines, both matter, and sometimes they decide the outcome.

Constants: a measured crossover

Searching a sorted list for its last element three ways: Python’s in operator, which is a linear scan written in C; a binary search written in Python; and bisect.bisect_left, which is binary search written in C. Times are per lookup and include about 30 ns of call overhead common to all three.

The O(n) scan in C beats the O(log n) search in Python up to about 32 elements, because each step of the C loop costs a couple of nanoseconds while each step of the Python loop costs tens. Past that, the growth rates take over, and at 8,192 elements the Python binary search is about 100 times faster. Implementing the same algorithm in C (bisect) gives roughly another factor of 5. Asymptotics decide what happens at scale; constants decide the small cases and the crossover point.

This is why library sorts switch to insertion sort below a cutoff, why hash tables with a handful of entries are often replaced by linear arrays, and why “use the algorithm with the better Big-O” is advice for large inputs only.

The memory hierarchy

The RAM model charges one step for any memory access. Real hardware has a hierarchy: registers, several levels of cache, main memory, and storage, each larger and slower than the one before. The machine used here reports a 64 KiB L1 data cache per core and a 16 MiB L2 cache shared by its performance cores. As rough orders of magnitude on current hardware, an L1 hit costs about a nanosecond and a DRAM access around 100 ns.

Caches load memory in lines of 64 or 128 bytes, and hardware prefetchers detect sequential access and fetch ahead. Access patterns that walk memory in order are therefore much cheaper per element than patterns that jump around, even when the operation count is identical.

The experiment below sums a list of Python integers in two orders. In both cases sum() reads the same $n$ integer objects, in a single pass, with the same number of operations. In the first list, the objects are laid out in memory in the order the list visits them, because they were allocated in that order. The second list holds the same objects in shuffled order, so each step jumps to an unrelated address.

xs = [i + 1000 for i in range(n)]      # int objects allocated in order
ys = xs[:]
random.shuffle(ys)                     # same objects, scattered order

           n   in order   shuffled  ratio   (ns per element, sum())
       1,000       2.22       2.12    1.0
      10,000       2.36       2.88    1.2
     100,000       2.83       3.35    1.2
   1,000,000       2.65      13.57    5.1
  10,000,000       2.67      15.93    6.0

Up to 100,000 elements the two orders cost about the same. Each integer object occupies 32 bytes, so 100,000 of them take about 3 MB and fit in the 16 MiB L2 cache once loaded. At 1,000,000 elements the objects take about 32 MB, the working set no longer fits, and the shuffled order becomes 5 times slower per element. The in-order version stays flat because the prefetcher keeps feeding it. Both versions are $\Theta(n)$, and Big-O correctly predicts that the total time grows linearly in each; it cannot predict the factor of 6 between them.

The same effect explains several standard engineering choices:

• Arrays usually beat linked lists, even for operations where the linked list has a better bound, because the array is contiguous and a list traversal is a chain of dependent cache misses (chapter 6).
• B-trees beat binary search trees on disk and in memory. A node holding hundreds of keys costs one block read, so the tree is shallow in terms of block transfers. PostgreSQL’s default index is a B-tree for this reason (Postgres indexes).
• Open addressing hash tables often beat chained ones, because probing neighboring slots stays within a cache line (chapter 8).
• Merge sort and quicksort both access memory sequentially during partition and merge, which is part of why they are fast in practice; heap sort jumps between index $i$ and $2i$, and is usually slower despite the same bound.

Models that account for memory

When memory transfers dominate, a different cost model gives better predictions. The external memory model (also called the I/O model or disk access model) has a fast memory of size $M$ and a slow memory accessed in blocks of size $B$, and counts only block transfers. Scanning $n$ items costs $\Theta(n/B)$ transfers, searching a B-tree costs $\Theta(\log_B n)$, and sorting costs $\Theta\big((n/B) \log_{M/B} (n/B)\big)$. Cache-oblivious algorithms achieve these bounds without knowing $M$ or $B$, typically by recursive divide-and-conquer that eventually produces subproblems that fit in each level of cache.

Other things Big-O does not capture

• Input size in bits. Trial division to test whether $n$ is prime takes $O(\sqrt{n})$ steps, which looks polynomial. The input is only $\log_2 n$ bits long, so in terms of input size the algorithm is exponential. Algorithms that are polynomial in the numeric value but not in the number of bits are called pseudo-polynomial. The dynamic programming solution to 0/1 knapsack, $O(nW)$ for capacity $W$, is the standard example (chapter 14).
• Hidden lower-order terms. An algorithm that runs in $n \log n + 10^6 n$ is $\Theta(n \log n)$, but the linear term dominates until $\log n$ exceeds a million.
• Parallelism. Work (total operations) and span (the longest chain of dependent operations) are separate measures. A parallel sum has $\Theta(n)$ work and $\Theta(\log n)$ span.
• Variance. Two algorithms with the same expected time can have very different tail latencies. Quicksort with random pivots has a tiny but nonzero probability of quadratic behavior; heap sort has none.

Summary