Asymptotic Analysis

In the previous lesson we saw the same algorithm, insertion sort, cost quadratically many comparisons on one input and linearly many on another, all on the same machine. To compare algorithms as algorithms, independent of the hardware and the particular input, we need two things: a model of computation abstract enough to ignore the machine, and a notation coarse enough to ignore constants. This lesson supplies both.

The RAM model of computation

We analyze algorithms against an idealized machine, the random-access machine (RAM). It has the properties all three books assume, usually tacitly:

• Instructions execute one at a time, no concurrency.
• The basic operations, namely arithmetic ($+$, $-$, $\times$, $/$), comparisons, data movement (load, store, copy), and control flow, each take a constant amount of time.
• Memory is an unbounded array of cells, and accessing any cell by its index costs the same constant (this is what random access means).
• Each cell holds an integer or float of reasonable size, roughly $O(\log n)$ bits for an input of size $n$, so a single value fits in a machine word.

The RAM is a deliberate fiction. Real multiplication is not truly constant-time for arbitrarily large numbers; real memory has caches that make some accesses far cheaper than others. But the model is predictive: an algorithm that is fast on the RAM is, overwhelmingly, fast in practice. Skiena stresses this engineering payoff;¹ CLRS is careful to flag the places, such as bignum arithmetic, where the constant-word assumption breaks down.²

From problem to $T(n)$

It helps to be precise about what we are even measuring. A computational problem is just a function $P:\mathcal{I}\to \mathcal{O}$ from a set of possible inputs to a set of possible outputs; each element $I\in \mathcal{I}$ is an instance of $P$. Sorting integer arrays, for example, has $\mathcal{I}=\left\{\text{all integer arrays}\right\}$. A size function $\mathrm{size}:\mathcal{I}\to \mathbb{N}$ records how big each instance is. For an array $⟨a_1,\dots ,a_n⟩$ we take $\mathrm{size}=n$. An algorithm $\mathcal{A}$ solves $P$ if $\mathcal{A}(I)=P(I)$ for every instance $I$.

Now charge ${\text{TimeCost}}^{\mathcal{A}}(I)$ = the number of elementary RAM operations $\mathcal{A}$ performs on input $I$. Inputs of the same size can cost different amounts, so we take the worst one of each size:

When the algorithm is understood, this is exactly the function we denote $T(n)$, the running time as a function of the input size $n$. The size is usually the number of elements, but sometimes the number of bits, or two parameters (e.g. $V$ and $E$ for a graph); choosing the right size measure is the first decision in any analysis. What we ultimately want is a good, convenient-to-understand upper bound on $T(n)$, which is precisely what the notation below provides.

Worst, average, and best case

For a fixed input size $n$, different inputs of that size may cost different amounts. Insertion sort costs $\Theta (n)$ on a sorted array and $\Theta (n^2)$ on a reversed one. So $T(n)$ is not one number; it is a range. We summarize it three ways:

• Worst case $T(n)$: the maximum cost over all inputs of size $n$.
• Best case: the minimum cost over all inputs of size $n$.
• Average case: the expected cost over a probability distribution on inputs of size $n$ (usually the uniform distribution).

We almost always report the worst case. It is a guarantee: the algorithm never does worse, no matter how adversarial the input. The best case is nearly useless as a promise, since any algorithm looks good on its luckiest input. The average case is the most honest predictor of typical performance but requires us to commit to a distribution, and the analysis is usually harder (it often needs the probabilistic tools of a later module). CLRS develops all three; Skiena argues that for design purposes the worst case is what you should plan for.

Why we drop constants and lower-order terms

Suppose careful counting gives the running time of some algorithm as

Two facts make most of this expression noise:

1. The leading term dominates. As $n$ grows, $3n^2$ swamps $50n+200$. At $n=1000$ the quadratic term is $3,000,000$ and the rest is $50,200$, under $2\%$. The growth rate is governed entirely by $n^2$.
2. The constants are machine artifacts. The $3$ depends on how many RAM operations our particular pseudocode spends per iteration; recompile on a different machine and it changes. It says nothing about the algorithm's intrinsic scaling.

So we throw both away and say the running time is order $n^2$. This is not sloppiness; it is the right level of abstraction. An $n^2$ algorithm with a tiny constant still loses eventually to an $n\log n$ algorithm with a large one, and eventually is exactly what asymptotic analysis captures. The notation below makes order $n^2$ precise.

The asymptotic notations

Let $f$ and $g$ be functions from the positive integers to the nonnegative reals. The notations describe how $f$ behaves relative to $g$ for all sufficiently large $n$.

Big-O: asymptotic upper bound

State it as a clean existential:

The constant $c$ lets us ignore multiplicative factors; the threshold $n_0$ lets us ignore small inputs where lower-order terms might still dominate. (CLRS phrases $O(g)$ as a set of functions and adds $0\le f(n)$ to keep things nonnegative; the two readings agree.)

The picture to keep in mind is the for large $n$ sketch: the scaled curve $cg(n)$ rises above $f(n)$ once $n$ passes the threshold $n_0$, and stays above forever after. What happens to the left of $n_0$ is irrelevant.

The wanted inequality method. Proofs of $O$-bounds follow a fixed recipe: write down the inequality you want to hold, then reverse-engineer constants $c$ and $n_0$ that make it true. To prove $3n^2+50n+200=O(n^2)$, we want $3n^2+50n+200\le c{n}^2$. For $n\ge 1$ each lower term is at most $n^2$, so $3n^2+50n+200\le 3n^2+50n^2+200n^2=253n^2$; thus $c=253$, $n_0=1$ work. The same move handles any polynomial; see the theorem below.

Big-Omega: asymptotic lower bound

Mirror the quantifiers, flip the inequality:

It is the mirror image of $O$: $f=O(g)$ if and only if $g=\Omega (f)$.

Big-Theta: asymptotic tight bound

$\Theta$ pins $f$ between two constant multiples of $g$: it grows exactly as fast as $g$, up to constants. The fundamental link is

When we say insertion sort is $\Theta (n^2)$ in the worst case, we mean its worst-case cost is sandwiched between $c_1{n}^2$ and $c_2{n}^2$, a precise, two-sided claim. When we only have an upper bound we say $O$; this is why people loosely write $O$ even where $\Theta$ holds. But the distinction matters, as the next two results make concrete.

The polynomial theorem

The single most useful fact for everyday analysis collapses every polynomial to its leading power:

Upper bound ($f=O(n^k)$). Replace every coefficient by its absolute value and every lower power by $n^k$ (valid for $n\ge 1$):

So define $c:=|a_k|+\cdots +|a_0|$ and pick $n_0=1$.

Lower bound ($f=\Omega (n^k)$). Pull out the leading term and bound the rest below; for $n\ge 1$,

The wanted inequality method now finds an $n_0$ past which the negative tail is, say, at most half of $a_k{n}^k$, leaving $f(n)\ge c{n}^k$ for all $n\ge n_0$. Together the two directions give $f(n)=\Theta (n^k)$: drop the constants and lower-order terms, keep the leading power.

$O$ is an upper bound, not a promise of tightness

Consider a worked cautionary case. Exchange sort compares $A[i]$ with $A[j]$ for every pair $i<j$, so its running time satisfies

by the polynomial theorem. But $O(n^2)$ also implies the true but useless statement $T(n)=O(n^3)$: a correct upper bound need not be tight. So how loose can we go? Not below $n^2$. The number of pairs is itself a lower bound on the work:

This forces $T(n)\ne O(n^{1.9})$; indeed $\frac{n^2}{2}-\frac{n}{2}\ne O(n^k)$ for any $k<2$. No constant $c$ can keep $\frac{n^2}{2}$ under $c{n}^{1.9}$ once $n$ is large enough, because $\frac{n^2}{2}>c{n}^{1.9}$ whenever $n>(2c{)}^{10}$. The moral: $O$ alone tells you the cost is no worse than something; only matching it with $\Omega$ (i.e. proving $\Theta$) certifies you have found the true growth rate.

Picture the exponents on a line. Exchange sort's cost $\Theta (n^2)$ sits at $k=2$. Every $O(n^k)$ with $k\ge 2$ is a valid upper bound, but only $k=2$ is tight; the $\Omega$ side forbids any upper bound with $k<2$, walling off the left. Where the two bounds meet is $\Theta$.

Little-o and little-omega: strict bounds

$O$ and $\Omega$ allow $f$ and $g$ to grow at the same rate. The lowercase versions forbid that; they assert a strict gap.

So $f=o(g)$ means $f$ becomes negligible compared to $g$: e.g. $n=o(n^2)$ and $\log n=o(n)$. Symmetrically, $f(n)=\omega (g(n))$ is defined by the reciprocal limit, ${\lim }_{n\to \infty }\frac{g(n)}{f(n)}=0⟺{\lim }_{n\to \infty }\frac{f(n)}{g(n)}=\infty ,$ so $f$ dominates $g$. A useful analogy from CLRS: $O,\Omega ,\Theta ,o,\omega$ are to functions as $\le ,\ge ,=,<,>$ are to numbers.

Comparing functions with limits

The limit of the ratio $f(n)/g(n)$ is how you rank growth rates:

To compare, say, $n^a$ and ${\log }^{b}n$ for any constants $a,b>0$, one shows the ratio ${\log }^{b}n/n^a\to 0$, so every polynomial beats every polylogarithm.³ Likewise $n^k=o(2^n)$ for every constant $k$: exponentials dominate all polynomials. A useful fact for sums: $\log (n!)=\Theta (n\log n)$ (by Stirling's approximation),⁴ which is why comparison sorts that do $\Theta (n\log n)$ work are optimal in a sense we will prove later.

Why we write $\log n$ with no base. Inside asymptotic notation the base is irrelevant, because changing base only multiplies by a constant:

So ${\log }_{2}n$, ${\log }_{10}n$, and $\ln n$ all live in the same $\Theta$-class, and $O(\log n)$ means the same thing whichever base you had in mind. (The constant $1/{\log }_{2}b$ is exactly the multiplicative factor $O$ and $\Omega$ are designed to absorb.)

The growth hierarchy

The functions algorithm designers meet most often, in strictly increasing order of growth, are:

Each row's growth dwarfs every row above it for large $n$. The practical dividing line Skiena draws is between polynomial time ($n^c$ for a constant $c$), generally considered tractable, and exponential time, which becomes hopeless very fast.⁵ A factorial-time algorithm that handles $n=12$ in a second needs years at $n=18$.

A sketch of the curves makes the separation clear. Even with a generous constant on the slower-growing function, the faster one wins past some crossover $n_0$:

Reading the cost off loops

Most analysis reduces to counting how many times each line runs. A few rules cover the common cases.

Sequential blocks add; we keep the max. If block $A$ costs $\Theta (n)$ and is followed by block $B$ costing $\Theta (n^2)$, the total is $\Theta (n)+\Theta (n^2)=\Theta (n^2)$: the larger term absorbs the smaller.

A simple loop multiplies the body by the iteration count. This nested fragment runs the constant-time body $n\cdot n$ times:

so its cost is $\Theta (n^2)$.

When the inner bound depends on the outer index, sum a series. If the inner loop runs $\text{for}j\leftarrow 1\text{to}i$, the body executes ${\sum }_{i=1}^{n}i=\frac{n(n+1)}{2}=\Theta (n^2)$ times — still quadratic, because triangular work is half of square work, and the constant $\frac{1}{2}$ vanishes. This is exactly the shape of insertion sort's worst case.

When the loop variable is scaled, take a logarithm. A loop that does $i\leftarrow i\times 2$ until $i>n$ runs about ${\log }_{2}n$ times, since $i$ doubles each pass. This is the source of every logarithm in algorithm analysis: repeatedly halving (or doubling) gives $\Theta (\log n)$ steps. Binary search and balanced-tree depth are the canonical examples.

The three loop shapes read off as area (or, for doubling, as the number of rungs). A square grid of iterations is $n^2$ work; bounding the inner loop by the outer index $i$ fills only the triangle below the diagonal, half as much but still $\Theta (n^2)$; and a doubling index touches just the ${\log }_{2}n$ powers of two.

Two more loop shapes round out the catalog, and both read off as areas just like the three above. An outer loop of $n$ passes wrapped around a doubling inner loop does ${\log }_{2}n$ work per pass — an $n\times \log n$ grid, $\Theta (n\log n)$. And a loop whose live problem halves every pass while doing linear work on what remains sums a geometric series $n+\frac{n}{2}+\frac{n}{4}+\cdots =2n$, so the whole stack of shrinking bars is no taller than two of the first — $\Theta (n)$.

The recurrences that arise when a loop is replaced by recursion, a function calling smaller copies of itself, need their own machinery, which is the subject of the next lesson.

Takeaways

• The RAM model charges constant time per primitive operation and lets us measure running time as a function $T(n)$ of input size, machine-independently.
• Report the worst case by default: it is a guarantee. Best case promises nothing; average case is honest but needs a distribution.
• Drop constants and lower-order terms. They are machine artifacts and noise; the leading term's growth rate is what scales.
• $O$ is an upper bound, $\Omega$ a lower bound, $\Theta$ a tight (two-sided) bound; $o$ and $\omega$ are their strict versions. $f=\Theta (g)\leftrightarrow f=O(g)$ and $f=\Omega (g)$.
• The limit $\lim f(n)/g(n)$ ranks two functions: $0$, a constant, or $\infty$ give $o$, $\Theta$, or $\omega$.
• Memorize the hierarchy $1\prec \log n\prec n\prec n\log n\prec n^2\prec 2^n\prec n!$; the polynomial/exponential boundary is the line between tractable and hopeless.