Growth Rates and Loop Analysis

This builds on Asymptotic Analysis, which defined the $O$ , $Ω$ , $Θ$ , $o$ , and $ω$ 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
$Θ (1)$	constant	array index, hash lookup (expected)
$Θ (log n)$	logarithmic	binary search
$Θ (n)$	linear	scan / find max
$Θ (n log n)$	linearithmic	merge sort, heapsort
$Θ (n^{2})$	quadratic	insertion sort (worst case)
$Θ (n^{3})$	cubic	naive matrix multiply
$Θ (2^{n})$	exponential	subset enumeration
$Θ (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.¹ 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.

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.

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:

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

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:

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.

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

Growth-rate curves for

log n

n

n^{2}

, and

2^{n}

growth_hierarchy.pypython

import math
from enum import IntEnum
from typing import Callable

class GrowthClass(IntEnum):
  """
    One rung of the growth hierarchy, ordered slowest to fastest.\n
    The integer value is the rank: a larger rank dominates a smaller one\n
    for all sufficiently large `n`, so the enum's natural ordering is the\n
    asymptotic ordering.\n
  """
  CONSTANT = 0
  LOGARITHMIC = 1
  LINEAR = 2
  LINEARITHMIC = 3
  QUADRATIC = 4
  CUBIC = 5
  EXPONENTIAL = 6
  FACTORIAL = 7

  @property
  def label(self) -> str:
    """
      The textbook name of this growth rate (e.g. "linearithmic").\n
    """
    return self.name.lower()

  def cost(self, size: int) -> float:
    """
      The representative cost of this class at input size `size`.\n
      Uses the canonical formula for the rung — 1, log2 n, n, n log2 n,\n
      n^2, n^3, 2^n, n! — so two classes can be compared numerically at\n
      any concrete size as well as asymptotically.\n
    """
    if size < 0:
      raise ValueError("size must be non-negative")
    formula: Callable[[int], float] = _COST_FORMULAS[self]
    return formula(size)

def _log2_or_zero(size: int) -> float:
  """
    log2(size) for size >= 1, and 0 at size 0 (an empty problem has no\n
    levels to descend), avoiding a domain error.\n
  """
  return math.log2(size) if size >= 1 else 0.0

_COST_FORMULAS: dict[GrowthClass, Callable[[int], float]] = {
  GrowthClass.CONSTANT: lambda size: 1.0,
  GrowthClass.LOGARITHMIC: _log2_or_zero,
  GrowthClass.LINEAR: lambda size: float(size),
  GrowthClass.LINEARITHMIC: lambda size: size * _log2_or_zero(size),
  GrowthClass.QUADRATIC: lambda size: float(size) ** 2,
  GrowthClass.CUBIC: lambda size: float(size) ** 3,
  GrowthClass.EXPONENTIAL: lambda size: float(2 ** size),
  GrowthClass.FACTORIAL: lambda size: float(math.factorial(size)),
}

def dominates(faster: GrowthClass, slower: GrowthClass) -> bool:
  """
    Whether `faster` grows strictly faster than `slower` — that is,\n
    `slower(n) = o(faster(n))`. True exactly when `faster` outranks\n
    `slower` on the hierarchy.\n
  """
  return faster > slower

def hierarchy() -> list[GrowthClass]:
  """
    The full hierarchy in increasing order of growth.\n
  """
  return sorted(GrowthClass)

def crossover(slow: GrowthClass, fast: GrowthClass, max_size: int = 100_000) -> int:
  """
    The smallest size `n >= 1` past which the faster class is at least as\n
    costly as the slower one and stays so — the threshold `n0` where the\n
    dominating curve overtakes for good.\n
    `fast` must outrank `slow`; raises if no crossover is found by\n
    `max_size`. (A scaled-up slow class can lead for a while; we want the\n
    first point beyond which the order never reverses.)\n
  """
  if not dominates(fast, slow):
    raise ValueError("fast must outrank slow on the hierarchy")

  # scan up from 1 for the first size where the faster curve catches up.
  for size in range(1, max_size + 1):
    if fast.cost(size) >= slow.cost(size):
      return size

  raise ValueError("no crossover found within max_size")

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 $Θ (n)$ and is followed by block $B$ costing $Θ (n^{2})$ , the total is $Θ (n) + Θ (n^{2}) = Θ (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:Counting work in nested loops

1
for $i \gets 1$ to $n$ do
2
for $j \gets 1$ to $n$ do
3
$c \gets c + A[i] \cdot B[j]$
$\Theta(1)$ body, $n^2$ times

so its cost is $Θ (n^{2})$ .

When the inner bound depends on the outer index, sum a series. If the inner loop runs $for j \leftarrow 1 to i$ , the body executes $\sum_{i = 1}^{n} i = \frac{n ( n + 1 )}{2} = Θ (n^{2})$ times — still quadratic, because triangular work is half of square work, and the constant $\frac{1}{2}$ 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 \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 $Θ (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 \leftarrow 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.

Reading loop cost as a shape, in order of growth — a constant loop touches one cell (

Θ (1)

); a doubling index visits

log_{2} n

rungs (

Θ (log n)

); a flat pass is linear (

Θ (n)

); an outer loop around a doubling inner loop fills an

n \times log n

grid (

Θ (n log n)

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, $\frac{1}{2} n^{2}$ , but the same $Θ (n^{2})$ once the constant is dropped. (A subtler linear case hides nearby: a loop that halves its live problem each pass does $n + \frac{n}{2} + \frac{n}{4} + \dots = 2 n$ total work, so it stays $Θ (n)$ despite touching every prefix.)

The two quadratic loop shapes. A full square grid of iterations is

n^{2}

work; an inner bound

j \leftarrow 1 \dots i

fills only the triangle below the diagonal,

\frac{1}{2} n^{2}

— half as much, but still

Θ (n^{2})

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:Naive all-subarray sums

1
for $i \gets 1$ to $n$ do
2
for $j \gets i$ to $n$ do
3
$s \gets 0$
4
for $k \gets i$ to $j$ do
5
$s \gets s + A[k]$
innermost body, $\Theta(1)$
6
print $s$

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

i = 1 \sum n j = i \sum n (j - i + 1) = i = 1 \sum n ℓ = 1 \sum n - i + 1 ℓ = i = 1 \sum n \frac{( n - i + 1 ) ( n - i + 2 )}{2},

after substituting $ℓ = j - i + 1$ and using $\sum_{ℓ = 1}^{m} ℓ = 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} (2 m + 1) = (3 n + 2)$ by the hockey-stick identity — that is, $\frac{1}{6} n (n + 1) (n + 2) = Θ (n^{3})$ .

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

$i \ 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: $\frac{1}{6} \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 $Θ (n^{2})$ of the pair-enumeration alone to $Θ (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 table lets each block sum be read in $Θ (1)$ , collapsing the whole routine to $Θ (n^{2})$ . Counting first tells you which loop to attack.

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.

loop_cost.pypython

from growth_hierarchy import GrowthClass

def linear_scan_cost(size: int) -> int:
  """
    Iterations of a single flat pass `for i in 1..n` — exactly `size`,\n
    the linear shape Theta(n).\n
  """
  _require_non_negative(size)
  return size

def square_loop_cost(size: int) -> int:
  """
    Iterations of two nested same-range loops `for i in 1..n / for j in\n
    1..n` — the full square grid, n^2, the quadratic shape Theta(n^2).\n
  """
  _require_non_negative(size)
  return size * size

def triangular_loop_cost(size: int) -> int:
  """
    Iterations when the inner bound follows the outer index\n
    (`for j in 1..i`): sum_{i=1}^{n} i = n(n+1)/2 — the triangle below the\n
    diagonal, half the square but still Theta(n^2). This is insertion\n
    sort's worst-case shape.\n
  """
  _require_non_negative(size)
  return size * (size + 1) // 2

def doubling_loop_cost(size: int) -> int:
  """
    Passes of a loop that does `i <- i * 2` until `i > n`, starting at 1.\n
    Doubling reaches n in floor(log2 n) + 1 passes for n >= 1 (one pass\n
    for n = 0, which never enters) — the logarithmic shape Theta(log n).\n
  """
  _require_non_negative(size)

  # double the index from 1 until it passes n, counting each pass.
  passes: int = 0
  index: int = 1
  while index <= size:
    passes += 1
    index *= 2

  return passes

def halving_total_work(size: int) -> int:
  """
    Total work of a loop that halves its live problem each pass:\n
    n + floor(n/2) + floor(n/4) + ... down to 0. The geometric series sums\n
    to under 2n, so despite touching every prefix the loop stays\n
    Theta(n) — the subtle linear case the lesson flags.\n
  """
  _require_non_negative(size)

  # add each live size while halving the problem down to 0.
  total: int = 0
  remaining: int = size
  while remaining > 0:
    total += remaining
    remaining //= 2

  return total

def growth_class_of_nesting(outer_exponent: int, inner_log_factor: bool = False) -> GrowthClass:
  """
    The growth class of a loop nest with `outer_exponent` plain nested\n
    passes (1 -> linear, 2 -> quadratic, 3 -> cubic), optionally wrapped\n
    around a doubling inner loop (`inner_log_factor=True`) that multiplies\n
    the cost by a log factor. Sequential blocks would instead keep the max\n
    of their classes — see `dominant_class`.\n
  """
  # a log inner factor bumps the plain nesting up one notch.
  if outer_exponent == 0 and not inner_log_factor:
    return GrowthClass.CONSTANT
  if outer_exponent == 0 and inner_log_factor:
    return GrowthClass.LOGARITHMIC
  if outer_exponent == 1 and inner_log_factor:
    return GrowthClass.LINEARITHMIC

  # plain nesting maps the exponent straight onto its polynomial class.
  table: dict[int, GrowthClass] = {
    1: GrowthClass.LINEAR,
    2: GrowthClass.QUADRATIC,
    3: GrowthClass.CUBIC,
  }
  if outer_exponent in table and not inner_log_factor:
    return table[outer_exponent]

  raise ValueError("unsupported loop nesting shape")

def dominant_class(blocks: list[GrowthClass]) -> GrowthClass:
  """
    The cost of sequential blocks: they add, and the largest term absorbs\n
    the smaller, so the total is the maximum growth class. An empty\n
    sequence does no work and is constant.\n
  """
  if not blocks:
    return GrowthClass.CONSTANT
  return max(blocks)

def _require_non_negative(size: int) -> None:
  """
    Guard: an input size cannot be negative.\n
  """
  if size < 0:
    raise ValueError("size must be non-negative")

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 $Θ (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 $Θ (n / B)$ transfers, and sorting costs $Θ (\frac{n}{B} log_{M / B} \frac{n}{B})$ .² 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.³ 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 $Θ (n^{log_{2} 7}) \approx Θ (n^{2.807})$ or plain $Θ (n^{3})$ still win for any feasible matrix.⁴ 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.⁵ 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 $Θ (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.⁶ Growth rates are where practical analysis and the deepest open question in the field meet.

Takeaways

Memorize the hierarchy $1 ≺ log n ≺ n ≺ n log n ≺ n^{2} ≺ n^{3} ≺ 2^{n} ≺ 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^{ε})$ for every $ε > 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 $Θ (n^{2})$ ), and a scaled index ( $i \leftarrow i \times 2$ ) gives $Θ (log n)$ steps.
Count before you optimize: the naive all-subarray sums routine hides a $Θ (n^{3})$ in a third loop whose length grows with the gap; a prefix-sum table removes it, dropping the cost to $Θ (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, §2 — Algorithm Analysis: the polynomial-vs-exponential dividing line between tractable and hopeless running times. ↩
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. ↩
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. ↩
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, 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. ↩
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. ↩

The growth hierarchy

Proving the orderings

Reading the cost off loops

A worked trace: three loops, one bound

When the cost model shifts

Takeaways

Footnotes