Asymptotic Complexity & Recurrences

Every other algorithms chapter depends on this one, because every claim about an algorithm's cost is stated in asymptotic notation and most of them are derived from a recurrence.

Asymptotic notation is a statement about growth, not about speed. Saying an algorithm is $O(n^2)$ says nothing about whether it takes a microsecond or an hour on any particular input. It says that as the input grows without bound, the running time grows no faster than the square.

The notation deliberately discards constants and lower-order terms, because those depend on the machine, the compiler and the implementation, while the growth rate depends on the algorithm. Discarding them is what makes the claim portable.

That discarding has a cost worth stating plainly. An $O(n\log n)$ algorithm can be slower than an $O(n^2)$ one on every input you will ever run, if its constant is large enough. Asymptotics tell you which wins eventually, not which wins today.

The second organising fact is that a recursive algorithm's cost is a recurrence, and a recurrence is read directly off the code. Count the recursive calls, note the subproblem size, add the work outside the calls. Everything after that is solving.

1. The Five Notations

Each notation bounds a function in a different direction, and the distinction is examined directly.

Formally, $f(n)=O(g(n))$ means there exist positive constants $c$ and $n_0$ such that

$0\le f(n)\le c\cdot g(n)$ for all $n\ge n_0$.

The two constants are what make the definition work. The constant $c$ absorbs any multiplicative factor and $n_0$ allows the bound to fail for small inputs, which is exactly why lower-order terms are irrelevant.

$\Theta$ is both $O$ and $\Omega$ simultaneously, so proving a tight bound means proving two inequalities rather than one.

Two remarks catch people out. $O$ is an upper bound and need not be tight, so writing that insertion sort is $O(n^3)$ is technically true and useless. And $O$ describes a function, not an algorithm, so an algorithm has different bounds for best, average and worst case, and stating one without saying which is ambiguous.

The relation $f=O(g)$ is not symmetric, so writing $O(g)=f$ is meaningless. The equals sign here is a historical abuse of notation for set membership.

2. Comparing Growth Rates

The hierarchy is worth memorising, because most questions are asking where a function sits in it.

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

Three rules settle almost every comparison.

Any polynomial beats any polylogarithm. $n^{0.001}$ eventually overtakes $(\log n{)}^{1000}$, however absurd that looks for practical $n$.

Any exponential beats any polynomial. $1.001^n$ eventually overtakes $n^{1000}$.

The base of a logarithm is irrelevant, since changing base multiplies by a constant, which $O$ absorbs. So ${\log }_{2}n$ and ${\log }_{10}n$ are both $\Theta (\log n)$. The base of an exponential is not irrelevant: $2^n$ and $3^n$ differ by an exponential factor, not a constant.

When the hierarchy does not settle a comparison directly, take logarithms of both functions and compare those, or apply L'Hopital's rule to the ratio.

A common trap is $n^{\log n}$ against $(\log n{)}^n$. Taking logarithms gives $(\log n{)}^2$ against $n\log \log n$, and the second is larger, so $(\log n{)}^n$ grows faster.

3. Analysing Loops

For iterative code, count how many times the innermost statement executes.

A loop running from 1 to $n$ with a constant increment executes $\Theta (n)$ times. A loop that multiplies its counter by a constant executes $\Theta (\log n)$ times, because the counter reaches $n$ after about $\log n$ multiplications.

Nested loops multiply when independent, but not when the inner bound depends on the outer counter.

For an inner loop running to the outer counter, the total is the sum $1+2+\cdots +n$, which is $\Theta (n^2)$ — the same as two independent loops, but the constant is halved.

A loop whose counter is squared each time executes $\Theta (\log \log n)$ times, since the exponent doubles and reaching $n$ needs $\log \log n$ doublings.

Conditional work inside a loop is bounded above by the worst case, but a tighter analysis sometimes shows the worst case cannot happen on every iteration — which is where amortised analysis begins.

4. Recurrences: Substitution and Recursion Trees

A recurrence for a divide-and-conquer algorithm has the shape $T(n)=aT(n/b)+f(n)$, where $a$ is the number of subproblems, $n/b$ their size, and $f(n)$ the work of dividing and combining.

The substitution method guesses a bound and proves it by induction. It is the only fully general method and the only one that produces a proof, but it requires the guess.

A frequent failure is to guess correctly and still fail the induction because the inductive hypothesis is too weak. Strengthening the hypothesis by subtracting a lower-order term often rescues it, which feels backwards and is standard practice.

The recursion tree method draws the recursion and sums the work level by level. It is the reliable way to generate the guess that substitution then proves.

At level $i$ there are $a^i$ nodes, each of size $n/b^i$, so the work at that level is $a^{i}f(n/b^i)$. The tree has ${\log }_{b}n$ levels, and the leaves number $a^{{\log }_{b}n}=n^{{\log }_{b}a}$.

Three outcomes are possible and they correspond exactly to the three master-theorem cases. Either the root dominates, or the leaves dominate, or every level contributes equally.

5. The Master Theorem

For $T(n)=aT(n/b)+f(n)$ with $a\ge 1$ and $b>1$, compare $f(n)$ against $n^{{\log }_{b}a}$.

That exponent is the critical quantity, and it is the total work at the leaves of the recursion tree.

Case 1 is leaf-dominated: the work shrinks going down the tree so fast that the leaves carry it all. Case 3 is root-dominated: the top level carries it all. Case 2 is balanced: every level contributes the same, and the extra logarithm counts the levels.

Case 3 carries a regularity condition that $af(n/b)\le cf(n)$ for some $c<1$, which ensures the work genuinely shrinks going down. It holds for every polynomial $f$ that appears in practice and is checked only when $f$ is unusual.

The theorem does not always apply. If $f$ is larger than $n^{{\log }_{b}a}$ but not polynomially larger — by a factor of only $\log n$, say — then no case fits, and a recursion tree is required.

The standard example of that gap is $T(n)=2T(n/2)+n/\log n$, which falls between cases 1 and 2.

6. Amortised Analysis

Amortised analysis bounds the average cost per operation over a worst-case sequence. It is not average-case analysis, because no probability is involved: the bound holds for every sequence, not for a typical one.

Three methods give the same answer with different bookkeeping.

The aggregate method bounds the total cost of $n$ operations and divides by $n$. It is the simplest and is usually enough.

The accounting method charges each operation more than it costs and banks the surplus to pay for later expensive operations, requiring only that the balance never goes negative.

The potential method defines a function of the data structure's state and charges each operation its actual cost plus the change in potential.

The potential must be chosen so that it starts at zero, never goes negative, and rises during cheap operations by enough to pay for the expensive ones later. For a doubling array, the potential is typically twice the number of elements past the halfway mark, which reaches the array's size exactly when a copy is due.

All three methods must give the same amortised bound, since they are bookkeeping devices rather than different analyses. The aggregate method is fastest when the total is easy to sum, and the potential method is preferred when several operations interact.

The canonical example is a dynamic array that doubles when full. A single append can cost $O(n)$ when a copy happens, but copies are rare: after a copy at size $n$, the next occurs at size $2n$. Summing the copy costs over $n$ appends gives $1+2+4+\cdots +n<2n$, so the amortised cost per append is $O(1)$.

The reason doubling works and adding a constant does not is that doubling makes the gaps between copies grow geometrically, while adding a fixed amount makes them constant, giving $\Theta (n)$ copies of average cost $\Theta (n)$ and a quadratic total.

7. Worked Examples

Example 1. Order these by growth rate: $n\log n$, $n^{1.5}$, $2^{\log n}$, $(\log n{)}^{\log n}$, $n!$.

Simplify what can be simplified first. $2^{\log n}$ with a base-2 logarithm is exactly $n$, so it is linear.

For $(\log n{)}^{\log n}$, take logarithms: $\log n\times \log \log n$. Compare with $n\log n$, whose logarithm is $\log n+\log \log n$, dominated by $\log n$. Since $\log n\log \log n$ exceeds $\log n$, the function $(\log n{)}^{\log n}$ grows faster than $n\log n$.

Compare $(\log n{)}^{\log n}$ with $n^{1.5}$, whose logarithm is $1.5\log n$. Dividing both logarithms by $\log n$ reduces the comparison to $\log \log n$ against the constant $1.5$, and $\log \log n$ exceeds $1.5$ for any reasonably large $n$. So the quasi-polynomial is larger.

Finally, $n!$ dominates everything here, since its logarithm is $\Theta (n\log n)$ by Stirling's approximation, which exceeds $\log n\log \log n$ by a wide margin.

The order is $2^{\log n}\prec n\log n\prec n^{1.5}\prec (\log n{)}^{\log n}\prec n!$.

The lesson is that taking logarithms is the reliable method whenever the hierarchy does not settle a comparison by inspection, because it converts exponents into products that can be compared term by term.

Example 2. Solve $T(n)=3T(n/4)+n\log n$ using the master theorem.

Identify $a=3$, $b=4$, and $f(n)=n\log n$.

Compute the critical exponent: ${\log }_{4}3\approx 0.792$, so $n^{{\log }_{b}a}\approx n^{0.792}$.

Compare $f(n)=n\log n$ against $n^{0.792}$. Since $n\log n$ grows faster than $n^{0.9}$, and $0.9>0.792$, we have $f(n)=\Omega (n^{{\log }_{4}3+ϵ})$ for $ϵ\approx 0.1$.

That is case 3, so check regularity: is $3f(n/4)\le cf(n)$ for some $c<1$?

$3\times (n/4)\log (n/4)=(3n/4)\log (n/4)\le (3/4)n\log n$, so $c=3/4<1$ and the condition holds.

Therefore $T(n)=\Theta (n\log n)$.

Example 3. Solve $T(n)=2T(n/2)+n/\log n$.

Identify $a=2$, $b=2$, so $n^{{\log }_{b}a}=n^1=n$.

Compare $f(n)=n/\log n$ against $n$. It is smaller, which suggests case 1 — but case 1 requires $f$ to be polynomially smaller, that is $O(n^{1-ϵ})$ for some positive $ϵ$.

It is not. The ratio $n/(n/\log n)=\log n$ grows more slowly than any positive power of $n$, so no $ϵ$ works. The master theorem does not apply.

Use a recursion tree. At level $i$ there are $2^i$ nodes of size $n/2^i$, so the level's work is

$2^i\times \frac{n/2^i}{\log (n/2^i)}=\frac{n}{\log n-i}$

Summing over $i$ from 0 to $\log n-1$ gives $n$ times the sum of $1/(\log n-i)$, which is $n$ times the harmonic series up to $\log n$.

That harmonic sum is $\Theta (\log \log n)$, so $T(n)=\Theta (n\log \log n)$.

This is the standard example of the master theorem's gap, and recognising the gap is more of the answer than the arithmetic.

Example 4. A loop runs for (i = 1; i < n; i = i * 3) containing an inner loop running for (j = 0; j < i; j++). What is the total cost?

The outer counter takes values $1,3,9,27,\dots$ up to $n$, so it runs ${\log }_{3}n$ times.

The inner loop runs $i$ times for each outer value, so the total is the sum of the outer values:

$1+3+9+\cdots +3^{\lfloor {\log }_{3}n\rfloor }$

This is a geometric series with ratio 3, and its sum is dominated by its last term, which is $\Theta (n)$.

Precisely, the sum equals $(3^{k+1}-1)/2$ where $3^k\le n$, which is $\Theta (n)$.

The total cost is $\Theta (n)$, not $\Theta (n\log n)$.

The trap is multiplying the loop counts. The outer loop runs $\log n$ times and the inner runs up to $n$ times, which suggests $n\log n$ — but the inner loop reaches $n$ only on the final iteration, and the geometric series is dominated by that single term.

Example 5. Prove by substitution that $T(n)=2T(n/2)+n$ is $O(n\log n)$.

Guess $T(n)\le cn\log n$ for some constant $c$ and all $n\ge n_0$.

Assume it holds for $n/2$: $T(n/2)\le c(n/2)\log (n/2)$.

Substitute into the recurrence:

$T(n)\le 2\cdot c\frac{n}{2}\log \frac{n}{2}+n=cn(\log n-1)+n=cn\log n-cn+n$

For this to be at most $cn\log n$, we need $-cn+n\le 0$, that is $c\ge 1$.

So the bound holds with $c=1$, provided the base case is satisfied — and for $n=2$, $T(2)\le 2\log 2=2$ requires the constant to be chosen large enough, which is always permitted since $n_0$ may be raised.

The induction closes, so $T(n)=O(n\log n)$.

Note the shape of the argument. The recurrence produced an extra $-cn$ term that had to absorb the $+n$, and that absorption is what fixed the constant. A guess of $O(n)$ would have failed here precisely because no such slack appears.

Example 6. A dynamic array doubles its capacity when full. Show that $n$ appends cost $O(n)$ in total, and explain why growing by a fixed increment does not.

Under doubling, a copy occurs when the array is full, at sizes $1,2,4,8,\dots$ up to $n$.

A copy at size $k$ costs $k$ operations, so the total copying cost is

$1+2+4+\cdots +n<2n$

because a geometric series with ratio 2 sums to less than twice its largest term.

Adding the $n$ appends themselves gives at most $3n$ operations for $n$ appends, so the amortised cost per append is $O(1)$.

Now consider growing by a fixed increment $k$. Copies occur at sizes $k,2k,3k,\dots ,n$, so there are $n/k$ copies, and the copy at size $ik$ costs $ik$.

The total is $k(1+2+\cdots +n/k)=k\cdot \frac{(n/k)(n/k+1)}{2}\approx \frac{n^2}{2k}$.

That is $\Theta (n^2)$ for any fixed $k$, so the amortised cost per append is $\Theta (n)$ rather than $O(1)$.

The difference is geometric versus arithmetic growth in the gaps between copies. Doubling makes each copy twice as rare as it is expensive, so the two effects cancel; a fixed increment makes copies equally frequent while they grow steadily more expensive.

Summary

Asymptotic notation describes growth, not speed, and discards constants and lower-order terms precisely because those depend on the machine rather than the algorithm.

$O$ is an upper bound, $\Omega$ a lower bound, $\Theta$ both, and $o$ and $\omega$ their strict versions. An upper bound need not be tight, and the notation describes a function rather than an algorithm, so best, average and worst case must be distinguished.

Any polynomial beats any polylogarithm and any exponential beats any polynomial. Logarithm bases are irrelevant; exponential bases are not. When the hierarchy does not settle a comparison, take logarithms.

Loop analysis counts innermost executions. A multiplying counter gives $\log n$ iterations, a squaring counter gives $\log \log n$, and nested loops multiply only when independent.

A divide-and-conquer recurrence is read off the code: number of calls, subproblem size, and work outside. Recursion trees generate the guess and substitution proves it, sometimes needing a strengthened hypothesis.

The master theorem compares $f(n)$ against $n^{{\log }_{b}a}$: polynomially smaller gives leaf domination, equal up to logs gives a balanced tree with one extra log, and polynomially larger with regularity gives root domination.

The theorem fails when $f$ differs by a non-polynomial factor, and $2T(n/2)+n/\log n$ is the standard example, solving to $\Theta (n\log \log n)$ by recursion tree.

Amortised analysis bounds the average over a worst-case sequence and involves no probability. Doubling a dynamic array gives $O(1)$ amortised appends because the gaps between copies grow geometrically, while a fixed increment gives $\Theta (n)$.