---
title: Growth Rates and Loop Analysis
module: Foundations
moduleNumber: 1
lessonNumber: 4
order: 104
summary: >
  With the asymptotic notations in hand, we rank the functions that actually
  arise in running times — from constant to factorial — proving the orderings
  between rungs, then read the running time of a loop nest straight off the page.
  Sequential blocks add, nested loops multiply, index scaling gives logarithms;
  a worked trace and a tour of cache-aware and galactic
  algorithms close the lesson.
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: 'Range Sum Query - Immutable'
    slug: range-sum-query-immutable
    difficulty: Easy
  - title: 'Running Sum of 1d Array'
    slug: running-sum-of-1d-array
    difficulty: Easy
  - title: 'Find Pivot Index'
    slug: find-pivot-index
    difficulty: Easy
  - title: 'Search a 2D Matrix'
    slug: search-a-2d-matrix
    difficulty: Medium
---

This builds on [Asymptotic Analysis](/algorithms/foundations/asymptotic-analysis),
which defined the $O$, $\Omega$, $\Theta$, $o$, and $\omega$ notations and the
limit test for ranking two functions. Here we put that machinery to work: we lay
out the growth classes algorithms meet in practice, prove the orderings between
them, and then reduce most everyday analysis to counting how many times a loop
body runs.

## The growth hierarchy

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

| Class | Name | A typical algorithm |
| :--- | :--- | :--- |
| $\Theta(1)$ | constant | array index, hash lookup (expected) |
| $\Theta(\log n)$ | logarithmic | binary search |
| $\Theta(n)$ | linear | scan / find max |
| $\Theta(n \log n)$ | linearithmic | merge sort, heapsort |
| $\Theta(n^2)$ | quadratic | insertion sort (worst case) |
| $\Theta(n^3)$ | cubic | naive matrix multiply |
| $\Theta(2^n)$ | exponential | subset enumeration |
| $\Theta(n!)$ | factorial | brute-force permutations (TSP) |

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.[^skiena-growth] A factorial-time algorithm that handles $n = 12$ in
a second needs years at $n = 18$.

### Proving the orderings

The table is really a chain of little-o claims: each class is $o$ of the one
below it. Every link yields to the two moves from the ratio test, L'Hôpital or a
substitution, so we prove three representative ones and leave the rest as
finger exercises.

> **Theorem.** For every constant $\varepsilon > 0$, $\log n = o(n^{\varepsilon})$.

> **Proof.** Substitute $n = 2^m$. The ratio becomes
> $$\frac{\log n}{n^{\varepsilon}} = \frac{m}{2^{\varepsilon m}},$$
> a linear function of $m$ against an exponential in $m$. Its $\log_2$ is
> $\log_2 m - \varepsilon m \to -\infty$ (since $\log_2 m = o(m)$ by L'Hôpital:
> $\lim_{x\to\infty} \ln x / x = \lim_{x\to\infty} (1/x)/1 = 0$), so the ratio
> tends to $0$. $\qed$

This is the sharpest form of "logs are cheap": $\log n$ grows more slowly than
$n^{0.01}$, than $n^{0.001}$, than any polynomial sliver at all. It is the
theorem behind every claim of the form "binary search's $O(\log n)$ beats a
linear scan."

> **Theorem.** $n \log n = o(n^2)$.

> **Proof.** Cancel the shared factor:
> $$\frac{n \log n}{n^2} = \frac{\log n}{n} \longrightarrow 0$$
> by the previous theorem with $\varepsilon = 1$. So merge sort's class sits
> strictly below insertion sort's worst case. $\qed$

> **Theorem.** $2^n = o(n!)$.

> **Proof.** Compare the two products factor by factor:
> $$
> \frac{n!}{2^n} = \prod_{i=1}^{n} \frac{i}{2}
> = \frac{1}{2} \cdot \frac{2}{2} \cdot \frac{3}{2} \cdots \frac{n}{2}
> \;\ge\; \frac{1}{2} \parens{\frac{3}{2}}^{\!n-2} \quad\text{for } n \ge 3,
> $$
> since every factor from $i = 3$ onward is at least $\tfrac32$. The right side
> tends to infinity, so $n!/2^n \to \infty$ and $2^n = o(n!)$. The same argument
> shows $c^n = o(n!)$ for _every_ constant $c$: once $i > 2c$, each factor $i/c$
> exceeds $2$, and the product runs away. The factorial outgrows every
> exponential. $\qed$

Chaining such results is painless because little-o is transitive: if $f = o(g)$
and $g = o(h)$, then $f = o(h)$ (the ratios multiply, and both factors vanish).
That single property turns the eight-row table into a totally ordered ladder.

Each class also has a characteristic _shape_ — a picture of how its work fills
space, from a single cell up to a tree that explodes:

$$
% caption: The growth hierarchy as shapes, in increasing order of growth: a single
%          cell (constant), a small block (logarithmic), a log n by log n square
%          (log-squared), a row (linear), an n by log n rectangle (linearithmic),
%          an n by n grid (quadratic), a cube (cubic), a doubling binary tree
%          (exponential), and a tree whose branching shrinks each level (factorial).
\tdplotsetmaincoords{60}{135}
\begin{tikzpicture}[font=\footnotesize, >=stealth,
  gcap/.style={align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  % ===== row 1: 1, log n, log^2 n =====
  \begin{scope}[shift={(0,0)}]
    \fill[acc!18] (1.1,0.95) rectangle ++(0.5,0.5);
    \draw[thick] (1.1,0.95) rectangle ++(0.5,0.5);
    \node[gcap] at (1.35,-0.4) {constant\\$1$};
  \end{scope}
  \begin{scope}[shift={(4.0,0)}]
    % constant work each step, but the index DOUBLES (1, 2, 4, ..., n), so only
    % log n steps are needed to reach n
    \draw[->] (0.4,0.7) -- (2.55,0.7) node[right, font=\scriptsize] {$i$};
    \foreach \x in {0.6,0.85,1.35,2.35} { \fill[acc] (\x,0.7) circle (1.4pt); }
    \draw[black!70, ->, shorten <=2.5pt, shorten >=2.5pt] (0.6,0.7) to[bend left=45] (0.85,0.7);
    \draw[black!70, ->, shorten <=2.5pt, shorten >=2.5pt] (0.85,0.7) to[bend left=45] (1.35,0.7);
    \draw[black!70, ->, shorten <=2.5pt, shorten >=2.5pt] (1.35,0.7) to[bend left=45] (2.35,0.7);
    \node[below, font=\scriptsize] at (0.6,0.66) {$1$};
    \node[below, font=\scriptsize] at (0.85,0.66) {$2$};
    \node[below, font=\scriptsize] at (1.35,0.66) {$4$};
    \node[below, font=\scriptsize] at (2.35,0.66) {$n$};
    \node[acc, font=\scriptsize] at (0.92,1.13) {doubles};
    \node[font=\scriptsize, text=black] at (1.45,1.52) {$\log n$ steps};
    \node[gcap] at (1.35,-0.4) {logarithmic\\$\log n$};
  \end{scope}
  \begin{scope}[shift={(8.0,0)}]
    \fill[acc!15] (0.9,0.5) rectangle ++(0.95,0.95);
    \draw[thick] (0.9,0.5) rectangle ++(0.95,0.95);
    % halving cuts on each side — the log n staircase idea, now in two dimensions,
    % so each side holds log n divisions (an uneven grid, unlike the n-by-n square)
    \draw[black, very thin] (1.375,0.5)--(1.375,1.45) (1.6125,0.5)--(1.6125,1.45) (1.73125,0.5)--(1.73125,1.45);
    \draw[black, very thin] (0.9,0.975)--(1.85,0.975) (0.9,1.2125)--(1.85,1.2125) (0.9,1.33125)--(1.85,1.33125);
    \node[font=\scriptsize] at (1.375,0.28) {$\log n$};
    \node[font=\scriptsize, rotate=90] at (0.68,0.975) {$\log n$};
    \node[gcap] at (1.35,-0.4) {log-squared\\$\log^2 n$};
  \end{scope}
  % ===== row 2: n, n log n, n^2 =====
  \begin{scope}[shift={(0,-3.1)}]
    \fill[acc!15] (0.35,1.0) rectangle ++(2.0,0.3);
    \draw[step=0.25, black, very thin] (0.35,1.0) grid ++(2.0,0.3);
    \draw[thick] (0.35,1.0) rectangle ++(2.0,0.3);
    \node[font=\scriptsize] at (1.35,1.55) {$n$};
    \node[gcap] at (1.35,-0.4) {linear\\$n$};
  \end{scope}
  \begin{scope}[shift={(4.0,-3.1)}]
    \fill[acc!15] (0.35,0.55) rectangle ++(2.0,0.75);
    \draw[step=0.25, black, very thin] (0.35,0.55) grid ++(2.0,0.75);
    \draw[thick] (0.35,0.55) rectangle ++(2.0,0.75);
    \node[font=\scriptsize] at (1.35,1.55) {$n$};
    \node[font=\scriptsize, rotate=90] at (0.18,0.92) {$\log n$};
    \node[gcap] at (1.35,-0.4) {linearithmic\\$n\log n$};
  \end{scope}
  \begin{scope}[shift={(8.0,-3.1)}]
    \fill[acc!15] (0.6,0.35) rectangle ++(1.5,1.5);
    \draw[step=0.1875, black, very thin] (0.6,0.35) grid ++(1.5,1.5);
    \draw[thick] (0.6,0.35) rectangle ++(1.5,1.5);
    \node[font=\scriptsize, fill=white, inner sep=0.6pt] at (1.35,1.1) {$n^2$};
    \node[font=\scriptsize] at (1.35,0.12) {$n$};
    \node[font=\scriptsize, rotate=90] at (0.38,1.1) {$n$};
    \node[gcap] at (1.35,-0.55) {quadratic\\$n^2$};
  \end{scope}
  % ===== row 3: n^3, 2^n, n! =====
  \begin{scope}[shift={(0,-6.4)}]
    % n^3 as an n-by-n grid of columns: indices i, j sweep the base (n x n), and the
    % height over each cell is the work for that (i, j) — a true 3-D bar chart via
    % tikz-3dplot (\tdplotsetmaincoords{60}{135} in the preamble). n*n cells, each up
    % to n tall, gives n^3. Bars are drawn far-corner-first for correct occlusion.
    \begin{scope}[shift={(0.72,0.66)}, scale=0.285]
      \begin{scope}[tdplot_main_coords]
        \draw[->, black, thin] (0,0,0) -- (4.5,0,0) node[anchor=north east, black, font=\scriptsize]{$i$};
        \draw[->, black, thin] (0,0,0) -- (0,4.5,0) node[anchor=north west, black, font=\scriptsize]{$j$};
        \draw[->, black, thin] (0,0,0) -- (0,0,2.5) node[anchor=south, black, font=\scriptsize]{work};
        % each (i,j) column does about n work; the n tick + dashed level make the
        % height legible, so n cells x n cells x n work reads as n^3.
        \draw[acc!60, dashed, very thin] (0,0,1.9) -- (4,0,1.9);
        \draw[black, thin] (-0.16,0,1.9) -- (0.08,0,1.9);
        \node[anchor=east, acc, font=\scriptsize] at (-0.2,0,1.9) {$n$};
        \foreach \i/\j in {3/0,3/1,2/0,3/2,2/1,1/0,3/3,2/2,1/1,0/0,2/3,1/2,0/1,1/3,0/2,0/3} {
          \pgfmathsetmacro{\h}{1.7+0.32*exp(-((\i-1.5)^2+(\j-1.5)^2)/3.2)}
          \pgfmathsetmacro{\xa}{\i+0.05}\pgfmathsetmacro{\xb}{\i+0.95}
          \pgfmathsetmacro{\ya}{\j+0.05}\pgfmathsetmacro{\yb}{\j+0.95}
          \fill[acc!34, draw=acc!70, very thin] (\xa,\ya,0)--(\xa,\yb,0)--(\xa,\yb,\h)--(\xa,\ya,\h)--cycle;
          \fill[acc!52, draw=acc!70, very thin] (\xa,\yb,0)--(\xb,\yb,0)--(\xb,\yb,\h)--(\xa,\yb,\h)--cycle;
          \fill[acc!18, draw=acc!70, very thin] (\xa,\ya,\h)--(\xb,\ya,\h)--(\xb,\yb,\h)--(\xa,\yb,\h)--cycle;
        }
      \end{scope}
    \end{scope}
    \node[gcap] at (1.15,-0.45) {cubic\\$n^3$};
  \end{scope}
  \begin{scope}[shift={(4.0,-6.4)}]
    \coordinate (r) at (1.35,1.7);
    \coordinate (a) at (0.9,1.1);  \coordinate (b) at (1.8,1.1);
    \coordinate (a1) at (0.65,0.5); \coordinate (a2) at (1.15,0.5);
    \coordinate (b1) at (1.55,0.5); \coordinate (b2) at (2.05,0.5);
    \draw[black] (r)--(a) (r)--(b) (a)--(a1) (a)--(a2) (b)--(b1) (b)--(b2);
    \foreach \p in {r,a,b,a1,a2,b1,b2} { \fill[acc] (\p) circle (1.5pt); }
    \node[gcap] at (1.35,-0.45) {exponential\\$2^n$};
  \end{scope}
  \begin{scope}[shift={(8.0,-6.4)}]
    % decreasing branching: root has 4 children, each child has 3 — the fan-out
    % shrinks level by level, the signature of n! = n(n-1)(n-2)...
    \coordinate (R) at (1.35,1.78);
    \coordinate (c1) at (0.45,1.12); \coordinate (c2) at (1.05,1.12);
    \coordinate (c3) at (1.65,1.12); \coordinate (c4) at (2.25,1.12);
    \draw[black] (R)--(c1) (R)--(c2) (R)--(c3) (R)--(c4);
    \foreach \cx in {0.45,1.05,1.65,2.25} {
      \draw[black] (\cx,1.12) -- ++(-0.2,-0.6) (\cx,1.12) -- ++(0,-0.6) (\cx,1.12) -- ++(0.2,-0.6);
    }
    \fill[acc] (R) circle (1.4pt);
    \foreach \p in {c1,c2,c3,c4} { \fill[acc] (\p) circle (1.3pt); }
    \foreach \cx in {0.45,1.05,1.65,2.25} {
      \fill[acc] ({\cx-0.2},0.52) circle (1.1pt);
      \fill[acc] (\cx,0.52) circle (1.1pt);
      \fill[acc] ({\cx+0.2},0.52) circle (1.1pt);
    }
    \node[gcap] at (1.35,-0.45) {factorial\\$n$!};
  \end{scope}
\end{tikzpicture}
$$

Those shapes come from _how_ the work is spent — the **step size** and the **work
done at each step**. The same hierarchy, read as work regimes:

$$
% caption: The same hierarchy as work regimes — the step size and the work at each
%          step that produce each rate. Doubling the index takes only log n steps;
%          stepping by one takes n; and when the work itself doubles or multiplies
%          each step, the total explodes.
\begin{tikzpicture}[font=\footnotesize, >=stealth,
  gcap/.style={align=center, font=\footnotesize},
  wk/.style={above, font=\scriptsize, text=black},
  bar/.style={fill=acc!18, draw=acc!55, very thin}]
  \definecolor{acc}{HTML}{2348F2}
  % ===== row 1: 1, log n, log^2 n =====
  \begin{scope}[shift={(0,0)}]
    \draw[->] (0.5,0.4) -- (2.3,0.4) node[midway, below, font=\scriptsize, text=black] {iteration};
    \draw[->] (0.5,0.4) -- (0.5,1.35) node[wk] {work};
    \draw[bar] (1.15,0.4) rectangle ++(0.3,0.6);
    \node[gcap] at (1.35,-0.5) {one step\\$1$};
  \end{scope}
  \begin{scope}[shift={(4.0,0)}]
    \draw[->] (0.5,0.45) -- (2.5,0.45) node[midway, below, font=\scriptsize, text=black] {iteration};
    \draw[->] (0.5,0.45) -- (0.5,1.4) node[wk] {work};
    \foreach \x in {0.75,1.0,1.5,2.4} { \fill[acc] (\x,0.7) circle (1.3pt); }
    \draw[black!70, ->, shorten <=2pt, shorten >=2pt] (0.75,0.7) to[bend left=42] (1.0,0.7);
    \draw[black!70, ->, shorten <=2pt, shorten >=2pt] (1.0,0.7) to[bend left=42] (1.5,0.7);
    \draw[black!70, ->, shorten <=2pt, shorten >=2pt] (1.5,0.7) to[bend left=42] (2.4,0.7);
    \node[acc, font=\scriptsize] at (1.05,1.15) {doubles};
    \node[gcap] at (1.35,-0.5) {index doubles\\$\log n$};
  \end{scope}
  \begin{scope}[shift={(8.0,0)}]
    \draw[->] (0.5,0.4) -- (2.6,0.4) node[midway, below, font=\scriptsize, text=black] {iteration};
    \draw[->] (0.5,0.4) -- (0.5,1.35) node[wk] {work};
    \foreach \x in {0.65,0.81,1.13,1.77,2.5} { \draw[bar] (\x,0.4) rectangle ++(0.12,0.62); }
    \node[acc, font=\scriptsize] at (1.55,1.22) {gaps double};
    \node[gcap] at (1.35,-0.5) {doubling steps, log work\\$\log^2 n$};
  \end{scope}
  % ===== row 2: n, n log n, n^2 =====
  \begin{scope}[shift={(0,-3.2)}]
    \draw[->] (0.5,0.45) -- (2.55,0.45) node[midway, below, font=\scriptsize, text=black] {iteration};
    \draw[->] (0.5,0.45) -- (0.5,1.4) node[wk] {work};
    \foreach \x in {0.7,0.92,1.14,1.36,1.58,1.8,2.02,2.24} { \fill[acc] (\x,0.7) circle (1.3pt); }
    \node[acc, font=\scriptsize] at (0.85,1.1) {$+1$};
    \node[gcap] at (1.35,-0.5) {index +1\\$n$};
  \end{scope}
  \begin{scope}[shift={(4.0,-3.2)}]
    \draw[->] (0.5,0.4) -- (2.55,0.4) node[midway, below, font=\scriptsize, text=black] {iteration};
    \draw[->] (0.5,0.4) -- (0.5,1.35) node[wk] {work};
    \foreach \x/\h in {0.6/0.22,0.85/0.34,1.1/0.44,1.35/0.52,1.6/0.59,1.85/0.65,2.1/0.70} { \draw[bar] (\x,0.4) rectangle ++(0.18,\h); }
    \node[gcap] at (1.4,-0.5) {+1 step, log work\\$n\log n$};
  \end{scope}
  \begin{scope}[shift={(8.0,-3.2)}]
    \draw[->] (0.5,0.4) -- (2.55,0.4) node[midway, below, font=\scriptsize, text=black] {iteration};
    \draw[->] (0.5,0.4) -- (0.5,1.4) node[wk] {work};
    \foreach \x/\h in {0.6/0.13,0.85/0.26,1.1/0.39,1.35/0.52,1.6/0.65,1.85/0.78,2.1/0.91} { \draw[bar] (\x,0.4) rectangle ++(0.18,\h); }
    \node[gcap] at (1.4,-0.5) {+1 step, $n$ work\\$n^2$};
  \end{scope}
  % ===== row 3: n^3, 2^n, n! =====
  \begin{scope}[shift={(0,-6.5)}]
    \draw[->] (0.5,0.4) -- (2.55,0.4) node[midway, below, font=\scriptsize, text=black] {iteration};
    \draw[->] (0.5,0.4) -- (0.5,1.4) node[wk] {work};
    \foreach \x/\h in {0.6/0.05,0.85/0.1,1.1/0.18,1.35/0.3,1.6/0.46,1.85/0.66,2.1/0.9} { \draw[bar] (\x,0.4) rectangle ++(0.18,\h); }
    \node[gcap] at (1.4,-0.5) {+1 step, $n^2$ work\\$n^3$};
  \end{scope}
  \begin{scope}[shift={(4.0,-6.5)}]
    % still n steps (7 bars across the same axis as its neighbours) — what differs
    % is that the work MULTIPLIES by a constant factor each step, not adds.
    \draw[->] (0.5,0.4) -- (2.55,0.4) node[midway, below, font=\scriptsize, text=black] {iteration};
    \draw[->] (0.5,0.4) -- (0.5,1.7) node[wk] {work};
    \foreach \x/\h in {0.6/0.05,0.85/0.08,1.1/0.13,1.35/0.22,1.6/0.36,1.85/0.58,2.1/0.92} { \draw[bar] (\x,0.4) rectangle ++(0.18,\h); }
    \node[acc, font=\scriptsize] at (1.3,1.6) {doubles each step};
    \node[gcap] at (1.4,-0.5) {$n$ steps, work doubles\\$2^n$};
  \end{scope}
  \begin{scope}[shift={(8.0,-6.5)}]
    % still n steps, but the factor itself grows (x2, x3, x4, ...) so it hugs the
    % floor then explodes harder than the geometric 2^n.
    \draw[->] (0.5,0.4) -- (2.55,0.4) node[midway, below, font=\scriptsize, text=black] {iteration};
    \draw[->] (0.5,0.4) -- (0.5,1.7) node[wk] {work};
    \foreach \x/\h in {0.6/0.02,0.85/0.035,1.1/0.06,1.35/0.12,1.6/0.26,1.85/0.55,2.1/0.97} { \draw[bar] (\x,0.4) rectangle ++(0.18,\h); }
    \node[acc, font=\scriptsize] at (1.35,1.6) {2x, 3x, 4x, ...};
    \node[gcap] at (1.4,-0.5) {$n$ steps, growing factor\\$n$!};
  \end{scope}
\end{tikzpicture}
$$

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

$$
% caption: Growth-rate curves for $\log n$, $n$, $n^2$, and $2^n$.
\begin{tikzpicture}[scale=0.85]
  \draw[->] (0,0) -- (5.6,0) node[right] {$n$};
  \draw[->] (0,0) -- (0,7.6) node[above] {$T(n)$};
  \draw[domain=0.05:5,smooth,thick] plot (\x, {0.55*ln(\x+1)})
    node[right] {$\log n$};
  \draw[domain=0:5,smooth,thick] plot (\x, {0.45*\x})
    node[right] {$n$};
  \draw[domain=0:4.5,smooth,thick] plot (\x, {0.22*\x*\x})
    node[right] {$n^2$};
  % 2^n: starts at the origin (exp(x)-1), crosses n^2 around n=3.6, then pulls
  % clear above it — the taller y-axis shows the exponential racing away.
  \draw[domain=0:4.5,smooth,thick] plot (\x, {0.08*(exp(\x)-1)})
    node[above] {$2^n$};
\end{tikzpicture}
$$

::impl{algo="growth_hierarchy"}

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

```algorithm
caption: Counting work in nested loops
for $i \gets 1$ to $n$ do
  for $j \gets 1$ to $n$ do
    $c \gets c + A[i] \cdot B[j]$ // $\Theta(1)$ body, $n^2$ 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 $\textbf{for}\ j \gets 1\ \textbf{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 $\tfrac12$
vanishes. This is the shape of insertion sort's worst case.

**When the loop variable is scaled, take a logarithm.** A loop that does
$i \gets 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.

Every loop nest has a _shape_, and its cost is the size of that shape — usually an
area, sometimes just a count of rungs. Lined up in order of growth, the common
shapes make the hierarchy concrete: a constant loop touches one cell; a _doubling_
index $i \gets i \times 2$ visits only the $\log_2 n$ powers of two; a flat pass is
linear; and an outer loop of $n$ passes wrapped around a doubling inner loop fills
an $n \times \log n$ grid.

$$
% caption: Reading loop cost as a shape, in order of growth — a constant loop touches one
%          cell ($\Theta(1)$); a doubling index visits $\log_2 n$ rungs ($\Theta(\log n)$); a
%          flat pass is linear ($\Theta(n)$); an outer loop around a doubling inner loop fills
%          an $n \times \log n$ grid ($\Theta(n\log n)$).
\begin{tikzpicture}[scale=0.95,>=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % --- panel 1: constant, a single cell ---
  \begin{scope}[shift={(0,0)}]
    \fill[acc!18] (0.2,0) rectangle (1.4,0.62);
    \draw[thick] (0.2,0) rectangle (1.4,0.62);
    \node[font=\footnotesize] at (0.8,0.31) {$a[\,i\,]$};
    \node[align=center] at (0.8,-0.95) {\footnotesize constant\\[-2pt]\footnotesize $1$};
  \end{scope}
  % --- panel 2: doubling, log n rungs ---
  \begin{scope}[shift={(2.0,0)}]
    \draw[->] (0,0) -- (2.6,0) node[right] {$i$};
    \foreach \x in {0.2,0.5,1.1,2.3} { \fill[acc] (\x,0.18) circle (1.5pt); }
    \draw[black!70, ->, shorten <=2.5pt, shorten >=2.5pt] (0.2,0.18) to[bend left=32] (0.5,0.18);
    \draw[black!70, ->, shorten <=2.5pt, shorten >=2.5pt] (0.5,0.18) to[bend left=32] (1.1,0.18);
    \draw[black!70, ->, shorten <=2.5pt, shorten >=2.5pt] (1.1,0.18) to[bend left=32] (2.3,0.18);
    \node[below, font=\footnotesize] at (0.2,0) {$1$};
    \node[below, font=\footnotesize] at (0.5,0) {$2$};
    \node[below, font=\footnotesize] at (1.1,0) {$4$};
    \node[below, font=\footnotesize] at (2.3,0) {$8$};
    \node[acc, font=\footnotesize] at (0.85,0.72) {doubles};
    \node[align=center] at (1.2,-0.95) {\footnotesize doubling\\[-2pt]\footnotesize $\log n$};
  \end{scope}
  % --- panel 3: linear, a number line stepping by one ---
  \begin{scope}[shift={(5.1,0)}]
    \draw[->] (0,0) -- (2.7,0) node[right] {$i$};
    \foreach \x in {0.25,0.65,1.05,1.45,1.85,2.25} { \fill[acc] (\x,0.16) circle (1.5pt); }
    \draw[black!70, ->, shorten <=2.5pt, shorten >=2.5pt] (0.25,0.16) to[bend left=45] (0.65,0.16);
    \draw[black!70, ->, shorten <=2.5pt, shorten >=2.5pt] (0.65,0.16) to[bend left=45] (1.05,0.16);
    \draw[black!70, ->, shorten <=2.5pt, shorten >=2.5pt] (1.05,0.16) to[bend left=45] (1.45,0.16);
    \draw[black!70, ->, shorten <=2.5pt, shorten >=2.5pt] (1.45,0.16) to[bend left=45] (1.85,0.16);
    \draw[black!70, ->, shorten <=2.5pt, shorten >=2.5pt] (1.85,0.16) to[bend left=45] (2.25,0.16);
    \node[below, font=\footnotesize] at (0.25,0) {$1$};
    \node[below, font=\footnotesize] at (0.65,0) {$2$};
    \node[below, font=\footnotesize] at (1.05,0) {$3$};
    \node[below, font=\footnotesize] at (1.45,0) {$4$};
    \node[below, font=\footnotesize] at (1.85,0) {$5$};
    \node[below, font=\footnotesize] at (2.25,0) {$6$};
    \node[acc, font=\footnotesize] at (0.45,0.58) {$+1$};
    \node[align=center] at (1.35,-0.95) {\footnotesize linear\\[-2pt]\footnotesize $n$};
  \end{scope}
  % --- panel 4: n log n as the area under a logarithmic work curve over 1..n ---
  \begin{scope}[shift={(8.4,0)}]
    \draw[->] (0,0) -- (2.95,0) node[right] {$i$};
    \draw[->] (0,0) -- (0,1.1) node[above, font=\footnotesize] {work};
    % work GROWS step by step like log i (linear vertical scale): each later step
    % does a little more (the per-step height climbs to log n), and the total area
    % is n log n
    \foreach \x/\h in {0.18/0.28,0.45/0.44,0.72/0.56,0.99/0.64,1.26/0.72,1.53/0.78,1.80/0.83,2.07/0.88,2.34/0.92} {
      \fill[acc!15] (\x,0) rectangle ++(0.18,\h);
      \draw[thin, acc!55] (\x,0) rectangle ++(0.18,\h);
    }
    \node[below, font=\footnotesize] at (0.27,0) {$1$};
    \node[below, font=\footnotesize] at (0.54,0) {$2$};
    \node[below, font=\footnotesize] at (0.81,0) {$3$};
    \node[below, font=\footnotesize] at (2.43,0) {$n$};
    \node[right, font=\scriptsize, black!70] at (2.55,0.92) {$\log n$};
    \node[font=\footnotesize] at (1.25,1.02) {$n\log n$};
    \node[align=center] at (1.3,-0.95) {\footnotesize doubling inner\\[-2pt]\footnotesize $n\log n$};
  \end{scope}
\end{tikzpicture}
$$

The two costliest shapes in everyday code are the quadratic ones. Two nested loops
over the same range fill a _square_ grid — $n^2$ work. Bounding the inner loop by
the outer index $i$ instead fills only the triangle below the diagonal: half as many
iterations, $\tfrac12 n^2$, but the same $\Theta(n^2)$ once the constant is dropped.
(A subtler linear case hides nearby: a loop that _halves_ its live problem each pass
does $n + \tfrac n2 + \tfrac n4 + \cdots = 2n$ total work, so it stays $\Theta(n)$
despite touching every prefix.)

$$
% caption: The two quadratic loop shapes. A full square grid of iterations is $n^2$ work; an
%          inner bound $j \gets 1 \dots i$ fills only the triangle below the diagonal,
%          $\tfrac12 n^2$ — half as much, but still $\Theta(n^2)$.
\begin{tikzpicture}[scale=1.0,>=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % --- panel 1: full square, n^2 ---
  \begin{scope}[shift={(0,0)}]
    \fill[acc!15] (0,0) rectangle (2.4,2.4);
    \draw[step=0.4,black,very thin] (0,0) grid (2.4,2.4);
    \draw[thick] (0,0) rectangle (2.4,2.4);
    \draw[->] (0,2.4) -- (0,2.9) node[above] {$i$};
    \draw[->] (2.4,0) -- (2.9,0) node[right] {$j$};
    \node[rotate=90, font=\footnotesize] at (-0.5,1.2) {$i$ = 1..$n$};
    \node at (1.2,-0.55) {\footnotesize $j$ = 1..$n$};
    \node[fill=white, inner sep=1.5pt] at (1.2,1.2) {$n^2$};
    \node[align=center] at (1.2,-1.5) {\footnotesize square loop\\[-2pt]\footnotesize quadratic};
  \end{scope}
  % --- panel 2: triangle, 1/2 n^2 ---
  \begin{scope}[shift={(4.1,0)}]
    \fill[acc!22] (0,0) -- (2.4,2.4) -- (0,2.4) -- cycle;
    \draw[step=0.4,black,very thin] (0,0) grid (2.4,2.4);
    \draw[thick] (0,0) rectangle (2.4,2.4);
    \draw[thick] (0,0) -- (2.4,2.4);
    \draw[->] (0,2.4) -- (0,2.9) node[above] {$i$};
    \draw[->] (2.4,0) -- (2.9,0) node[right] {$j$};
    \node[rotate=90, font=\footnotesize] at (-0.5,1.2) {$i$ = 1..$n$};
    \node at (1.2,-0.55) {\footnotesize $j$ = 1..$i$};
    \node[fill=white, inner sep=1.5pt] at (0.75,1.7) {$n^2$/2};
    \node[align=center] at (1.2,-1.5) {\footnotesize triangular loop\\[-2pt]\footnotesize still quadratic};
  \end{scope}
\end{tikzpicture}
$$

### A worked trace: three loops, one bound

Rules are easier to trust once you have watched them settle a real fragment. Take
a routine that, given an array $A$ of $n$ numbers, prints the sum of every
contiguous block $A[i..j]$ the slow way — recomputing each block's sum from
scratch:

```algorithm
caption: Naive all-subarray sums
for $i \gets 1$ to $n$ do
  for $j \gets i$ to $n$ do
    $s \gets 0$
    for $k \gets i$ to $j$ do
      $s \gets s + A[k]$    // innermost body, $\Theta(1)$
    print $s$
```

Count the innermost body. For a fixed pair $(i, j)$ it runs $j - i + 1$ times, so
the total is

$$
\sum_{i=1}^{n} \sum_{j=i}^{n} (j - i + 1)
= \sum_{i=1}^{n} \sum_{\ell=1}^{\,n-i+1} \ell
= \sum_{i=1}^{n} \frac{(n-i+1)(n-i+2)}{2},
$$

after substituting $\ell = j - i + 1$ and using $\sum_{\ell=1}^{m} \ell =
m(m+1)/2$. Let $m = n - i + 1$ run from $n$ down to $1$ as $i$ climbs, and the
outer sum becomes $\sum_{m=1}^{n} \binom{m+1}{2} = \binom{n+2}{3}$ by the
hockey-stick identity — that is, $\tfrac16 n(n+1)(n+2) = \Theta(n^3)$.

Pin it down with real numbers at $n = 4$. The block lengths $j - i + 1$ over all
$\binom{4}{2} + 4 = 10$ pairs $(i, j)$ are:

| $i \backslash j$ | 1 | 2 | 3 | 4 |
| :--- | :-: | :-: | :-: | :-: |
| **1** | 1 | 2 | 3 | 4 |
| **2** |   | 1 | 2 | 3 |
| **3** |   |   | 1 | 2 |
| **4** |   |   |   | 1 |

Summing the entries gives $1+2+3+4+1+2+3+1+2+1 = 20$ innermost additions, and the
closed form checks: $\tfrac16 \cdot 4 \cdot 5 \cdot 6 = 20$. The cubic is real,
not an over-count — the third nested loop, whose length _grows with_ the gap
$j - i$, is what lifts the cost from the $\Theta(n^2)$ of the pair-enumeration
alone to $\Theta(n^3)$.

The lesson the trace teaches is where the cost hides. A reader who stops at "two
visible loops, so $n^2$" is wrong by a full factor of $n$; the inner
`for $k$` loop supplies that factor. It is also removable: a running [prefix-sum](/algorithms/sequences/prefix-sums)
table lets each block sum be read in $\Theta(1)$, collapsing the whole routine to
$\Theta(n^2)$. Counting first tells you _which_ loop to attack.


The [recurrences](/algorithms/foundations/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.

::impl{algo="loop_cost"}

## When the cost model shifts

The RAM model's flat, unit-cost memory is the assumption that ages worst. On real
hardware a cache miss can cost hundreds of times what a hit does, so two
algorithms with identical $\Theta(n)$ RAM counts can differ by an order of
magnitude in wall-clock time. The **external-memory (I/O) model** of Aggarwal and
Vitter (1988) charges for block transfers between a fast memory of size $M$ and a
slow disk moved in blocks of size $B$, and counts I/Os rather than instructions;
scanning $n$ items costs $\Theta(n/B)$ transfers, and sorting costs
$\Theta\!\big(\tfrac{n}{B}\log_{M/B}\tfrac{n}{B}\big)$.[^av-io] Frigo, Leiserson,
Prokop, and Ramachandran (1999) pushed this further with **cache-oblivious**
algorithms, which achieve the optimal transfer count for _every_ block size at
once, without ever naming $B$ or $M$ — recursive layouts like the van Emde Boas
tree do this automatically.[^cache-oblivious] The _cost model_ is itself a
modeling choice: pick the one whose expensive operation matches your bottleneck.

A second modern wrinkle sharpens "constants don't matter." They do not matter
_asymptotically_, but the crossover can sit past every input anyone will run. An
algorithm whose asymptotic bound only beats its rivals for astronomically large
$n$ is called **galactic**. The canonical case is matrix multiplication: the
Coppersmith–Winograd family and its descendants drive the exponent below $2.372$,
yet the hidden constants and structure make them useless in practice, where
Strassen's $\Theta(n^{\log_2 7}) \approx \Theta(n^{2.807})$ or plain
$\Theta(n^3)$ still win for any feasible matrix.[^galactic] The lesson mirrors
"small inputs lie" from the previous lesson: an asymptotic verdict is a statement
about the limit, and engineering lives before the limit.

Finally, the polynomial-versus-exponential line the hierarchy draws is the same
line complexity theory draws between **P**, the problems solvable in polynomial
time, and the harder classes. Cobham (1965) and Edmonds (1965) independently
proposed polynomial time as the formal stand-in for "efficient," which is why the
hierarchy treats $n^c$ as tractable and $2^n$ as hopeless.[^cobham-edmonds] Whether
every problem whose solutions can be _checked_ in polynomial time can also be
_solved_ in polynomial time — the **P versus NP** question — remains open, and a
great many natural problems (the traveling-salesman tour whose brute force sits at
the $\Theta(n!)$ bottom of our table among them) are **NP-complete**: a
polynomial-time algorithm for any one would give a polynomial-time algorithm for
all.[^np-complete] Growth rates are where practical analysis and the deepest
open question in the field meet.

## Takeaways

- Memorize the hierarchy $1 \prec \log n \prec n \prec n\log n \prec n^2 \prec n^3
  \prec 2^n \prec n!$; each rung is $o$ of the next, and little-o's transitivity
  makes the table a totally ordered ladder.
- The orderings are proved with the ratio test: $\log n = o(n^\varepsilon)$ for
  every $\varepsilon > 0$, $n\log n = o(n^2)$, and $2^n = o(n!)$ — indeed
  $c^n = o(n!)$ for every constant $c$, so the factorial outgrows every
  exponential.
- The polynomial/exponential boundary is the line between tractable and hopeless:
  a factorial-time routine that handles $n = 12$ in a second needs years at
  $n = 18$.
- Read loop cost by counting: **sequential blocks add** (keep the max), **nested
  loops multiply** the body by the iteration count, an **index-dependent inner
  bound** sums a series (a triangle is still $\Theta(n^2)$), and a **scaled index**
  ($i \gets i \times 2$) gives $\Theta(\log n)$ steps.
- Count before you optimize: the naive all-subarray sums routine hides a
  $\Theta(n^3)$ in a third loop whose length grows with the gap; a prefix-sum table
  removes it, dropping the cost to $\Theta(n^2)$.
- The cost model is a choice. The external-memory and cache-oblivious models count
  block transfers instead of instructions when memory hierarchy dominates; galactic
  algorithms win asymptotically but never in practice; and the
  polynomial/exponential line is the same one **P** versus **NP** is drawn on.

[^skiena-growth]: **Skiena**, §2 — Algorithm Analysis: the polynomial-vs-exponential dividing line between tractable and hopeless running times.
[^av-io]: Aggarwal, A. & Vitter, J. S. (1988). "The input/output complexity of sorting and related problems." _Communications of the ACM_ 31(9). Introduces the external-memory model and the sorting I/O bound.
[^cache-oblivious]: Frigo, M., Leiserson, C. E., Prokop, H. & Ramachandran, S. (1999). "Cache-oblivious algorithms." _Proc. 40th FOCS_. Algorithms optimal across all block/cache sizes without naming them.
[^galactic]: Le Gall, F. (2014). "Powers of tensors and fast matrix multiplication." _Proc. ISSAC_ — the sub-$2.373$ exponent; the term "galactic algorithm" is due to R. J. Lipton and K. Regan for bounds that only help at astronomically large inputs. Strassen, V. (1969). "Gaussian elimination is not optimal." _Numerische Mathematik_ 13.
[^cobham-edmonds]: Cobham, A. (1965). "The intrinsic computational difficulty of functions." _Proc. Logic, Methodology and Philosophy of Science_. Edmonds, J. (1965). "Paths, trees, and flowers." _Canadian J. Mathematics_ 17 — polynomial time as the formal notion of "efficient."
[^np-complete]: Cook, S. A. (1971). "The complexity of theorem-proving procedures." _Proc. 3rd STOC_; Karp, R. M. (1972). "Reducibility among combinatorial problems." NP-completeness and the P-vs-NP question.