---
title: Asymptotic Analysis
module: Foundations
moduleNumber: 1
lessonNumber: 3
order: 103
summary: >
  We measure an algorithm's running time as a function of its input size, then
  strip away machine-specific constants and lower-order terms to compare
  algorithms cleanly. This lesson defines the RAM model and the $O$, $\Omega$,
  $\Theta$, $o$, and $\omega$ notations, proves the polynomial theorem, and shows
  how to rank growth rates with the limit test, L'Hôpital, base substitution, and
  the logarithm identities the arguments lean on.
topics: [Asymptotic Analysis]
sources:
  - book: CLRS
    ref: "Ch. 3 — Characterizing Running Times"
  - book: Skiena
    ref: "§2 — Algorithm Analysis"
  - book: Erickson
    ref: "Appendix — Solving Recurrences; analysis throughout"
practice:
  - title: 'Best Time to Buy and Sell Stock'
    slug: best-time-to-buy-and-sell-stock
    difficulty: Easy
  - title: 'Contains Duplicate'
    slug: contains-duplicate
    difficulty: Easy
  - title: 'Majority Element'
    slug: majority-element
    difficulty: Easy
  - title: 'Squares of a Sorted Array'
    slug: squares-of-a-sorted-array
    difficulty: Easy
  - title: 'Maximum Subarray'
    slug: maximum-subarray
    difficulty: Medium
---

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 CLRS, Skiena, and Erickson all 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;[^skiena-ram] CLRS is careful to flag the places, such as bignum
arithmetic, where the constant-word assumption breaks down.[^clrs-ram]

### 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} = \set{\text{all integer arrays}}$. A **size** function
$\size : \mathcal{I} \to \mathbb{N}$ records how "big" each instance
is. For an array $\langle a_1, \dots, a_n\rangle$ we take $\size =
n$. An algorithm $\mathcal{A}$ **solves** $P$ if $\mathcal{A}(I) = P(I)$ for every
instance $I$.

Now charge $\textsc{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:

$$
\textsc{MaxCost}^{\mathcal{A}}(n) \;=\; \max_{\substack{I \in \mathcal{I} \\ \size(I) = n}} \textsc{TimeCost}^{\mathcal{A}}(I).
$$

When the algorithm is understood, this is 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 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).

$$
% caption: For each fixed size $n$, the cost is a _range_: best at the bottom edge, worst
%          at the top, average in between. The shaded band is the spread over all inputs
%          of that size. Slicing at one chosen size $n_0$ pins the three cases to three
%          points on the vertical — the runtime of any single input of size $n_0$ lands
%          somewhere on that segment.
\begin{tikzpicture}[scale=1.0,>=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \draw[->] (0,0) -- (6.4,0) node[right] {$n$};
  \draw[->] (0,0) -- (0,5.0) node[above] {$T(n)$};
  % spread between best (bottom) and worst (top); average runs strictly between
  \fill[acc!15]
    plot[domain=0:5.4,smooth] (\x,{0.30*\x + 0.09*\x*\x})
    -- plot[domain=5.4:0,smooth] (\x,{0.30*\x})
    -- cycle;
  \draw[domain=0:5.4,smooth,thick] plot (\x,{0.30*\x + 0.09*\x*\x}) node[right] {worst};
  \draw[domain=0:5.4,smooth,thick,dashed] plot (\x,{0.30*\x + 0.045*\x*\x}) node[right] {average};
  \draw[domain=0:5.4,smooth,thick] plot (\x,{0.30*\x}) node[right] {best};
  % slice at one fixed size n_0: the three cases are three points on it
  \draw[dotted] (4.0,0) -- (4.0,2.64);
  \foreach \fy in {1.2,1.92,2.64} \fill (4.0,\fy) circle (1.3pt);
  \draw[<->, acc] (4.35,1.2) -- (4.35,2.64) node[midway, right, font=\footnotesize, fill=white, inner sep=1pt] {range at $n_0$};
  \node[below] at (4.0,0) {$n_0$};
  \node[acc, font=\footnotesize, fill=white, inner sep=1.5pt] at (2.55,0.9) {spread over inputs};
\end{tikzpicture}
$$

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
$$
T(n) = 3n^2 + 50n + 200.
$$
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 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 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:

> **Definition (Big-O).** $f(n) = O(g(n))$ means
> $$\exists\, c > 0 \;\; \exists\, n_0 > 0 \;\; \forall\, n \ge n_0 : \; f(n) \le c\,g(n).$$
> In words, "$f$ is **upper bounded by $g$, up to a constant factor**." Roughly,
> $f \preccurlyeq g$.

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
$c\,g(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.

$$
% caption: Curve $c \cdot g(n)$ rises above $f(n)$ once $n$ passes the _**threshold**_
%          $n_0$.
\begin{tikzpicture}[scale=1.0,>=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \draw[->] (0,0) -- (5.6,0) node[right] {$n$};
  \draw[->] (0,0) -- (0,7.3) node[above] {};
  % f(n): grows, but is dominated past n0
  \draw[domain=0:5,smooth,thick,black] plot (\x, {0.45*\x + 0.10*\x*\x})
    node[right] {$f(n)$};
  % c*g(n): the dominating bound — crosses f(n) exactly at n0 = 2.5 (y = 1.75)
  \draw[domain=0:5,smooth,thick,acc] plot (\x, {0.28*\x*\x})
    node[above right] {$c\,g(n)$};
  % crossover threshold n0: f(2.5) = cg(2.5) = 1.75, so the marker sits on the meet
  \draw[dashed] (2.5,0) -- (2.5,1.75);
  \node[below] at (2.5,0) {$n_0$};
  \fill (2.5,1.75) circle (1.4pt);
  \node[align=center] at (4.2,0.55) {\footnotesize $f(n) \le c\,g(n)$\\[-2pt]\footnotesize for $n \ge n_0$};
\end{tikzpicture}
$$

**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:

> **Definition ($\Omega$).** $f(n) = \Omega(g(n))$ means
> $$\exists\, c > 0 \;\; \exists\, n_0 > 0 \;\; \forall\, n \ge n_0 : \; f(n) \ge c\,g(n).$$
> "$f$ grows **at least** as fast as $g$." Roughly, $f \succcurlyeq g$.

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

### Big-Theta: asymptotic tight bound

> **Definition ($\Theta$).** $\Theta(g(n))$ is the set of functions $f(n)$ for which there exist positive
> constants $c_1, c_2, n_0$ such that
> $$0 \le c_1\,g(n) \le f(n) \le c_2\,g(n) \quad\text{for all } n \ge n_0.$$

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

$$
f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \ \text{and}\ f(n) = \Omega(g(n)).
$$

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 show.

### The polynomial theorem

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

> **Theorem (Polynomial growth).** If $f(n) = a_k n^k + a_{k-1}n^{k-1} + \cdots + a_1 n + a_0$ is a
> polynomial with $a_k > 0$, then $f(n) = \Theta(n^k)$.

> **Proof.** We prove the two directions separately.
>
> _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$):
> $$
> f(n) \le |a_k|n^k + |a_{k-1}|n^k + \cdots + |a_0|n^k = \parens{|a_k| + \cdots + |a_0|}\,n^k = c\,n^k.
> $$
> 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$,
> $$
> f(n) \ge a_k n^k - \parens{|a_{k-1}|n^{k-1} + \cdots + |a_0|} \ge a_k n^k - \parens{|a_{k-1}| + \cdots + |a_0|}\,n^{k-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. $\qed$

::impl{algo="polynomial_growth"}

### $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

$$
T(n) \;\le\; a\cdot\frac{n(n-1)}{2} = \frac{a}{2}n^2 - \frac{a}{2}n = O(n^2)
$$

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:

$$
T(n) \;\ge\; |S| = \binom{n}{2} = \frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2}.
$$

This forces $T(n) \neq O(n^{1.9})$; indeed $\tfrac{n^2}{2} - \tfrac{n}{2} \neq
O(n^k)$ for **any** $k < 2$. No constant $c$ can keep $\tfrac{n^2}{2}$ under
$c\,n^{1.9}$ once $n$ is large enough, because $\tfrac{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$.

$$
% caption: Valid bounds for exchange sort's $\Theta(n^2)$ cost, by exponent. Every
%          $O(n^k)$ with $k\ge 2$ holds but only $k=2$ is tight; $\Omega(n^2)$ rules out
%          the whole region below $k=2$. The bounds pinch shut exactly at $\Theta(n^2)$.
\begin{tikzpicture}[scale=1.0,>={Stealth[length=2.4mm]}]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-0.5,-1.9) rectangle (8.6,1.7);
  % forbidden region k<2 (Omega wall)
  \fill[red!12] (0,-0.18) rectangle (3.0,0.18);
  % valid-but-loose O region k>2
  \fill[acc!15] (3.0,-0.18) rectangle (8.0,0.18);
  \draw[->] (-0.2,0) -- (8.5,0) node[right] {$k$};
  \foreach \x/\t in {1/1, 1.9/1.9, 3/2, 5/2.5, 7/3} {
    \draw (\x,0.13) -- (\x,-0.13);
    \node[below=1.5mm, font=\footnotesize] at (\x,-0.13) {\t};
  }
  % tight point at k=2
  \fill[acc] (3.0,0) circle (2.2pt);
  \node[acc, font=\footnotesize, align=center, above=3mm] at (3.0,0.13) {tigh\/t\\[-1pt]bound};
  % labels
  \node[font=\footnotesize, red!75!black, align=center, below=4mm] at (1.45,-0.5) {ruled out by the lower bound\\(no $O(n^k)$ with $k$ below 2)};
  \node[font=\footnotesize, acc, align=center] at (5.7,1.15) {valid $O(n^k)$ but loose};
  \draw[acc, ->] (5.7,0.92) -- (5.5,0.22);
\end{tikzpicture}
$$

### 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.

> **Definition (Little-o).** $f(n) = o(g(n))$ means $f(n)$ is **less than _any_ constant times $g(n)$**: for
> **every** constant $c > 0$ there is an $n_0$ with $f(n) < c\,g(n)$ for all
> $n \ge n_0$. There is also an equivalent limit form,
> $$f(n) = o(g(n)) \iff \lim\limits_{n\to\infty} \frac{f(n)}{g(n)} = 0.$$

> **Definition (Little-ω).** $f(n) = \omega(g(n))$ means $f(n)$ **eventually
> exceeds _every_ constant times** $g(n)$: for **every** constant $c > 0$ there is
> an $n_0$ with $f(n) > c\,g(n)$ for all $n \ge n_0$. Its limit form is the
> reciprocal of little-o's,
> $$f(n) = \omega(g(n)) \iff \lim\limits_{n\to\infty} \frac{f(n)}{g(n)} = \infty.$$

So $f = o(g)$ means $f$ becomes _negligible_ compared to $g$ ($n = o(n^2)$,
$\log n = o(n)$), and $f = \omega(g)$ means $f$ _dominates_ $g$ ($n^2 = \omega(n)$,
$n = \omega(\log n)$) — mirror images, since $f = o(g) \iff g = \omega(f)$. A useful
analogy from CLRS: $O, \Omega, \Theta, o, \omega$ are to functions as
$\le, \ge, =, <, >$ are to numbers.

$$
% caption: Each asymptotic notation mirrors a comparison on numbers:
%          $o,O,\Theta,\Omega,\omega$ line up with $<,\le,=,\ge,>$. The little-o and
%          little-omega ends are _strict_ (they forbid equal growth), exactly as $<$ and
%          $>$ are strict. One example per column: $n = o(n^2)$, $\;2n = O(n)$,
%          $\;3n^2 = \Theta(n^2)$, $\;n^2 = \Omega(n)$, $\;2^n = \omega(n^2)$.
\begin{tikzpicture}[
    nb/.style={draw, minimum width=20mm, minimum height=8mm, font=\footnotesize, align=center},
    lbl/.style={font=\footnotesize},
    >={Stealth[length=2.4mm]}]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-4.7,-3.7) rectangle (10.7,1.1);
  \node[lbl, anchor=east] at (-1.7,0) {notation};
  \node[lbl, anchor=east] at (-1.7,-1.9) {comparison};
  % notation row — strict ends tinted, the tight middle shaded
  \node[nb, fill=acc!12] (o)  at (0.3,0) {little-o};
  \node[nb] (O)  at (2.65,0) {big-O};
  \node[nb, fill=black!7] (Th) at (5.0,0) {big-Theta};
  \node[nb] (Om) at (7.35,0) {big-Omega};
  \node[nb, fill=acc!12] (w)  at (9.7,0) {little-omega};
  % comparison row — text-mode ASCII comparators
  \node[nb, fill=acc!12] (lt) at (0.3,-1.9) {$<$};
  \node[nb] (le) at (2.65,-1.9) {$\le$};
  \node[nb, fill=black!7] (eq) at (5.0,-1.9) {=};
  \node[nb] (ge) at (7.35,-1.9) {$\ge$};
  \node[nb, fill=acc!12] (gt) at (9.7,-1.9) {$>$};
  \draw[->, black] (o) -- (lt);
  \draw[->, black] (O) -- (le);
  \draw[->, black] (Th) -- (eq);
  \draw[->, black] (Om) -- (ge);
  \draw[->, black] (w) -- (gt);
  % the underlying spectrum: slower growth on the left, faster on the right
  \draw[<->, black] (0.3,-2.85) -- (9.7,-2.85);
  \node[lbl, anchor=north] at (0.3,-3.0) {$f$ slower};
  \node[lbl, anchor=north] at (5.0,-3.0) {same rate};
  \node[lbl, anchor=north] at (9.7,-3.0) {$f$ faster};
  % the strict (open) ends — they forbid equal growth
  \node[lbl, red!75!black, font=\scriptsize] at (0.3,0.7) {strict};
  \node[lbl, red!75!black, font=\scriptsize] at (9.7,0.7) {strict};
\end{tikzpicture}
$$

### Strict implies loose, never the reverse

Little-o strengthens $O$. If $f(n) = o(g(n))$, then the inequality
$f(n) < c\,g(n)$ holds in particular for $c = 1$ past some threshold, and $c = 1$
with that threshold witnesses $f = O(g)$. So $o(g) \subseteq O(g)$, and by the mirror
argument $\omega(g) \subseteq \Omega(g)$. The containment is proper, and the
counterexample is as small as they come:

> **Claim.** $2n = O(n)$ but $2n \neq o(n)$.

> **Proof.** For the $O$-bound take $c = 2$ and $n_0 = 1$: certainly $2n \le 2n$.
> For the failure of little-o, recall the definition demands $f(n) < c\,g(n)$ for
> _every_ $c > 0$; take $c = 1$. We would need $2n < n$ for all large $n$, which
> holds for no $n$ at all. Equivalently,
> $\lim_{n\to\infty} 2n/n = 2 \neq 0$. $\qed$

The picture to hold: $o(g)$ is the part of $O(g)$ that keeps a widening gap below
$g$, and $\Theta(g)$ is the part that tracks $g$ exactly. The two cannot overlap:
if $f = o(g)$ then $f$ eventually drops below $c_1\,g$ for every candidate lower
constant $c_1$, so no $\Omega(g)$ bound, and hence no $\Theta(g)$ bound, can hold.
The sets $o(g)$, $\Theta(g)$, and $\omega(g)$ are pairwise disjoint, which is
precisely what the strict/tight/strict labels in the figure record.

One warning before leaning on the number analogy too hard. Real numbers obey
trichotomy: for any $a, b$, exactly one of $a < b$, $a = b$, $a > b$ holds.
Functions do not. CLRS's example is $n$ versus $n^{1 + \sin n}$: the exponent
oscillates between $0$ and $2$ forever, so the second function is neither $O(n)$
nor $\Omega(n)$, and the pair cannot be ranked at all.[^clrs-incomparable]
Asymptotic comparison is a partial order, not a total one. In practice the
running times we meet are comparable, but proofs should never _assume_ two
functions can be ordered.

::impl{algo="asymptotic_relation"}

## Comparing functions with limits

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

$$
\lim\limits_{n\to\infty} \frac{f(n)}{g(n)} =
\begin{cases}
0 & \Rightarrow f = o(g) \ (\text{so also } f = O(g)) \\
c \in (0,\infty) & \Rightarrow f = \Theta(g) \\
\infty & \Rightarrow f = \omega(g) \ (\text{so also } f = \Omega(g)).
\end{cases}
$$

$$
% caption: The three outcomes of the ratio test. Plot $f(n)/g(n)$ against $n$: a ratio
%          sinking to $0$ certifies $f = o(g)$; a ratio settling at a constant $c > 0$
%          certifies $f = \Theta(g)$; a ratio climbing without bound certifies
%          $f = \omega(g)$.
\begin{tikzpicture}[scale=1.0,>=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \draw[->] (0,0) -- (6.6,0) node[right] {$n$};
  \draw[->] (0,0) -- (0,4.6) node[above] {$f(n)/g(n)$};
  % omega: climbs without bound
  \draw[domain=0:5.6,smooth,thick,acc] plot (\x,{0.35+0.105*\x*\x})
    node[right, font=\footnotesize] {grows: little-omega};
  % Theta: settles at the constant c
  \draw[dashed, black] (0,1.8) -- (5.5,1.8);
  \node[left, font=\footnotesize] at (0,1.8) {$c$};
  \draw[domain=0:5.8,smooth,thick] plot (\x,{1.8-1.35*exp(-0.55*\x)})
    node[right, font=\footnotesize] {settles: big-Theta};
  % o: sinks to 0
  \draw[domain=0:5.8,smooth,thick,black] plot (\x,{0.9*exp(-0.6*\x)+0.04});
  \node[black, font=\footnotesize, anchor=west] at (3.05,0.55) {sinks to 0: little-o};
\end{tikzpicture}
$$

One caution. The test is sufficient, not necessary: the limit may fail to exist
even when a $\Theta$-bound holds. The function $f(n) = (2 + (-1)^n)\,n$ hops
between $n$ and $3n$ forever, so $f(n)/n$ has no limit, yet $f = \Theta(n)$ with
$c_1 = 1$ and $c_2 = 3$. When the ratio oscillates, fall back on the quantifier
definitions; they are the ground truth, and the limit forms are a convenience
layered on top.[^clrs-limits]

### The ratio test, worked three times

The method: form the ratio, simplify it until its limit is readable, and apply
the case table above. Three comparisons cover the
moves that recur in practice.

**1. $n \log n$ vs $n^{1.1}$: L'Hôpital on the leftover.** Divide out the shared
factor of $n$ first:

$$
\frac{n \log n}{n^{1.1}} = \frac{\log n}{n^{0.1}}.
$$

Numerator and denominator both tend to infinity, and both are differentiable as
functions of a real variable $x$, so L'Hôpital's rule applies (switch to $\ln$;
the base costs only a constant factor):

$$
\lim_{x \to \infty} \frac{\ln x}{x^{0.1}}
= \lim_{x \to \infty} \frac{1/x}{0.1\,x^{-0.9}}
= \lim_{x \to \infty} \frac{10}{x^{0.1}} = 0.
$$

So $n \log n = o(n^{1.1})$: any polynomial exponent strictly above $1$, however
slightly, eventually outgrows $n \log n$. The crossover is remote, though. The
ratio only drops below $1$ once $\log_2 n < n^{0.1}$, which first happens around
$n \approx 2^{59}$, on the order of $10^{17}$. For every input you will ever
benchmark, $n \log n$ _looks_ bigger; the limit says the polynomial wins anyway.

**2. Polylogs vs polynomials: substitute $n = 2^m$.** Claim: for all constants
$a, b > 0$,

$$
(\log n)^b = o(n^a),
$$

so **every** polynomial beats **every** polylogarithm.[^erickson-growth] The
ratio $(\log n)^b / n^a$ mixes a log and a power awkwardly; the fix is a change
of variable. Set $n = 2^m$ (so $m = \log_2 n$, and $m \to \infty$ exactly when
$n \to \infty$):

$$
\frac{(\log n)^b}{n^a} \;=\; \frac{m^b}{(2^m)^a} \;=\; \frac{m^b}{2^{am}}.
$$

$$
% caption: The substitution $n = 2^m$ turns an awkward polylog-vs-polynomial race in $n$
%          into a familiar polynomial-vs-exponential race in $m$: $\log^b n$ vs $n^a$
%          becomes $m^b$ vs $2^{am}$, and the exponential wins.
\begin{tikzpicture}[font=\footnotesize, >=stealth,
    box/.style={draw, align=center, inner xsep=3mm, inner ysep=2.5mm}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (L) at (0,0) {awkward race in $n$\\$\log^b n$ vs $n^a$};
  \node[box, fill=acc!8] (R) at (6.6,0) {familiar race in $m$\\$m^b$ vs $2^{am}$};
  \draw[->, thick, acc] (L) -- (R) node[midway, above, acc] {set $n = 2^m$};
  \node[black] at (3.3,-1.2) {polynomial vs exponential: the exponential wins};
\end{tikzpicture}
$$

This is now a polynomial in $m$ against an exponential in $m$.
Take $\log_2$ of the ratio:

$$
\log_2 \frac{m^b}{2^{am}} = b \log_2 m - am
= -am\parens{1 - \frac{b}{a}\cdot\frac{\log_2 m}{m}} \longrightarrow -\infty,
$$

because $\log_2 m / m \to 0$ (the $b = 1$, exponent-$1$ case of comparison 1).
A quantity whose logarithm tends to $-\infty$ tends to $0$, so the ratio
vanishes and the claim holds. Erickson's slogan for the general principle: take
logs until the comparison becomes one you already know.

**3. $n^k$ vs $2^n$: take the log of the ratio.** The same move settles
polynomials against exponentials directly:

$$
\log_2 \frac{n^k}{2^n} = k \log_2 n - n \longrightarrow -\infty,
$$

since $\log_2 n = o(n)$ by comparison 2. Hence $n^k / 2^n \to 0$, i.e.
$n^k = o(2^n)$ for **every** fixed $k$; even $n^{100}$ is eventually dominated by
$2^n$. Read backwards, $2^n = \omega(n^k)$: no polynomial upper bound of any
degree can hold for an exponential.

### Small inputs lie

Comparison 2 comes with the same caveat as comparison 1: the crossover
can sit far beyond any table of test values. Take $b = 4$, $a = 1$, that is,
$\log^4 n$ against $n$. The two are equal exactly when $m^4 = 2^m$ for
$m = \log_2 n$, and $m = 16$ gives $16^4 = 65{,}536 = 2^{16}$ on both sides. So
the polylog stays **above** the polynomial for every $n$ up to $65{,}536$, and
near $n \approx 55$ it is ahead by a factor of about $20$. An empirical plot
stopping at $n = 10{,}000$ would rank the two backwards; the limit gets it
right.

$$
% caption: Small inputs lie. The vertical axis is the ratio of $\log^4 n$ to $n$ on a
%          log scale, so the horizontal axis is the ratio-$1$ line. The polylog runs
%          ahead (ratio above $1$, peaking near $20\times$ around $n \approx 55$) all
%          the way to the crossover at $n = 2^{16} = 65{,}536$ — only then does the
%          polynomial pull ahead for good.
\begin{tikzpicture}[scale=1.0,>=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % axes: x is n (marked at powers of 2), y is log of the ratio, so y=0 means ratio 1
  \draw[->] (-0.2,0) -- (6.9,0) node[right] {$n$};
  \draw[->] (0.31,-1.9) -- (0.31,2.9) node[above, font=\footnotesize] {ratio};
  \node[anchor=east, font=\scriptsize, black] at (0.24,-0.32) {ratio 1};
  \foreach \m/\lab in {4/{$2^4$}, 8/{$2^8$}, 12/{$2^{12}$}, 20/{$2^{20}$}} {
    \draw ({0.31*\m},0.07) -- ({0.31*\m},-0.07);
    \node[below=1mm, font=\scriptsize] at ({0.31*\m},-0.07) {\lab};
  }
  % the ratio curve: y = 0.55*(4*log2 m - m), zero exactly at m=16
  \draw[domain=1:20,smooth,thick,acc]
    plot ({0.31*\x},{0.55*(5.7708*ln(\x) - \x)});
  % crossover at m=16, i.e. n = 2^16 = 65536
  \fill[acc] (4.96,0) circle (1.8pt);
  \node[below=1mm, font=\scriptsize, acc] at (4.96,-0.07) {$2^{16}$};
  \draw[acc!70, ->] (5.35,1.05) -- (5.05,0.12);
  \node[acc, font=\footnotesize, align=center] at (5.85,1.62) {crossover at\\$n$ = 65536};
  \node[font=\footnotesize, black] at (1.85,2.75) {polylog ahead};
  \node[font=\footnotesize, black] at (5.9,-1.3) {polynomial ahead};
\end{tikzpicture}
$$

**Why we write $\log n$ with no base.** Inside asymptotic notation the base is
irrelevant, because changing base only multiplies by a constant:
$$
\log_b n = \frac{\log_2 n}{\log_2 b} = \Theta(\log_2 n) \quad\text{for every constant } b > 1.
$$
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 the multiplicative factor $O$ and $\Omega$ are designed to
absorb.)

### The logarithm identities analysis leans on

Base-changing is one of a small kit of identities that carry most asymptotic
arguments involving logs:[^skiena-logs]

$$
\log(ab) = \log a + \log b, \qquad
\log(a^b) = b \log a, \qquad
\log_b a = \frac{\log_c a}{\log_c b}.
$$

Each has a specific role. The product rule turns products into
sums, which is how one analyzes anything defined multiplicatively; the log of
$n! = 1 \cdot 2 \cdots n$ becomes the sum $\sum_{i=1}^{n} \log i$, handled
below. The power rule pulls exponents out front, so
$\log(n^c) = c \log n = \Theta(\log n)$: the logarithm of any polynomial in $n$
is just $\Theta(\log n)$, degree notwithstanding. And base-change is the license
to write bare $\log n$.

One less familiar identity swaps a base against an exponent:

> **Theorem (Exponent swap).** For all $a, b, c > 0$ with $b \neq 1$,
> $$a^{\log_b c} = c^{\log_b a}.$$

> **Proof.** Apply $\log_b$ to both sides. The left side gives
> $\log_b c \cdot \log_b a$ by the power rule; the right side gives
> $\log_b a \cdot \log_b c$. The two agree, and $\log_b$ is injective, so the
> originals were equal. $\qed$

Its use is cosmetic but constant: it rewrites an exponential _in_ $\log n$ as a
plain polynomial. For instance $3^{\log_2 n} = n^{\log_2 3} \approx n^{1.585}$,
a shape that will fall out of divide-and-conquer
[recurrences](/algorithms/foundations/recurrences) and would otherwise be hard
to place in the hierarchy.

Finally, the sum $\sum \log i$ promised above:

> **Theorem.** $\log(n!) = \Theta(n \log n)$.

> **Proof.** Work in base $2$. By the product rule,
> $\log(n!) = \sum_{i=1}^{n} \log i$.
>
> _Upper bound._ Each of the $n$ terms is at most $\log n$, so
> $\log(n!) \le n \log n$.
>
> _Lower bound._ Keep only the top half of the terms, those with $i > n/2$;
> there are at least $n/2$ of them, and each is at least $\log(n/2) = \log n - 1$.
> Hence
> $$
> \log(n!) \;\ge\; \frac{n}{2}\parens{\log n - 1} \;\ge\; \frac{n}{4} \log n
> \quad\text{once } \log n \ge 2, \text{ i.e. } n \ge 4.
> $$
> Together, $c_1 = \tfrac14$, $c_2 = 1$, $n_0 = 4$ witness
> $\log(n!) = \Theta(n \log n)$. $\qed$

Stirling's approximation sharpens the same statement to
$\log(n!) = n \log n - \Theta(n)$,[^clrs-stirling] but the half-the-terms trick
above is the version worth internalizing; it reappears whenever a sum needs a
quick lower bound. This bound is also why
[comparison sorts](/algorithms/sorting/sorting-lower-bounds) that do
$\Theta(n \log n)$ work are optimal in a sense we will prove later.


With the notations defined and the ranking machinery in hand, the next lesson
puts them to work: it lays out the standard growth hierarchy, proves the orderings
between its rungs, and shows how to read the running time of a loop nest straight
off the page. This continues in
[Growth Rates and Loop Analysis](/algorithms/foundations/growth-rates-and-loop-analysis).

## 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) \iff f = O(g)$
  and $f = \Omega(g)$.
- $O$ alone certifies only that the cost is _no worse than_ something; matching it
  with $\Omega$ (proving $\Theta$) is what pins the true growth rate. Comparison is
  a partial order — some function pairs, like $n$ and $n^{1+\sin n}$, cannot be
  ranked at all.
- The limit $\lim f(n)/g(n)$ ranks two functions: $0$, a constant, or $\infty$
  give $o$, $\Theta$, or $\omega$. When the ratio is hard to evaluate, take its logarithm or
  substitute $n = 2^m$ until the comparison becomes one you know.
- **Small inputs lie.** $\log^4 n$ exceeds $n$ for every $n$ up to $65{,}536$,
  and $n \log n$ looks larger than $n^{1.1}$ out past $10^{17}$; only the limit
  verdict is final.
- Logarithms: the base never matters inside $\Theta$; $\log$ turns products into
  sums; $a^{\log_b c} = c^{\log_b a}$ turns exponentials in $\log n$ into plain
  polynomials; and $\log(n!) = \Theta(n \log n)$ by the half-the-terms trick.

[^skiena-ram]: **Skiena**, §2 — Algorithm Analysis: the RAM model as a machine-independent abstraction whose engineering payoff is predicting real-world speed.
[^clrs-ram]: **CLRS**, Ch. 3 — Characterizing Running Times: the RAM model's constant-word assumption and where it breaks down (e.g. bignum arithmetic).
[^clrs-stirling]: **CLRS**, Ch. 3 — Characterizing Running Times: $\log(n!) = \Theta(n\log n)$ via Stirling's approximation.
[^erickson-growth]: **Erickson**, _Algorithms_, Appendix — Solving Recurrences (analysis throughout): ranking growth rates by the limit of the ratio, so every polynomial dominates every polylogarithm.
[^clrs-limits]: **CLRS**, Ch. 3 — Characterizing Running Times: the limit characterizations of $o$ and $\omega$; the quantifier definitions remain the ground truth when the limit does not exist.
[^clrs-incomparable]: **CLRS**, Ch. 3 — Characterizing Running Times: asymptotic comparability is not total; $n$ and $n^{1+\sin n}$ cannot be ranked.
[^skiena-logs]: **Skiena**, §2 — Algorithm Analysis: logarithm identities and their consequences for analysis, including why the base is irrelevant inside asymptotic notation.