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 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;¹ 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 : I \to O$ from a set of possible inputs to a set of possible outputs; each element $I \in I$ is an instance of $P$ . Sorting integer arrays, for example, has $I = {all integer arrays}$ . A size function $size : I \to N$ records how big each instance is. For an array $⟨ a_{1}, \dots, a_{n} ⟩$ we take $size = n$ . An algorithm $A$ solves $P$ if $A (I) = P (I)$ for every instance $I$ .

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

MaxCost^{A} (n) = I \in I size (I) = n max TimeCost^{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 $Θ (n)$ on a sorted array and $Θ (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).

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.

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) = 3 n^{2} + 50 n + 200.

Two facts make most of this expression noise:

The leading term dominates. As $n$ grows, $3 n^{2}$ swamps $50 n + 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}$ .
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:

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 \leq 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.

Curve

c \cdot g (n)

rises above

f (n)

once

n

passes the threshold

n_{0}

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 $3 n^{2} + 50 n + 200 = O (n^{2})$ , we want $3 n^{2} + 50 n + 200 \leq c n^{2}$ . For $n \geq 1$ each lower term is at most $n^{2}$ , so $3 n^{2} + 50 n + 200 \leq 3 n^{2} + 50 n^{2} + 200 n^{2} = 253 n^{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 = Ω (f)$ .

Big-Theta: asymptotic tight bound

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

f (n) = Θ (g (n)) \leftrightarrow f (n) = O (g (n)) and f (n) = Ω (g (n)) .

When we say insertion sort is $Θ (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 $Θ$ 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:

polynomial_growth.pypython

from typing import NamedTuple, Sequence

class BoundWitness(NamedTuple):
  """
    A constant `c` and threshold `n0` certifying f(n) <= c * n^degree for\n
    every n >= n0 — the pair an O-bound proof must exhibit.\n
  """
  constant: float
  threshold: int

class Polynomial:
  """
    A polynomial stored by its coefficients, lowest power first.\n
    `coefficients[index]` is the multiplier on n^index, so\n
    [200, 50, 3] represents 3 n^2 + 50 n + 200.\n
  """

  def __init__(self, coefficients: Sequence[float]) -> None:
    if not coefficients:
      raise ValueError("a polynomial needs at least one coefficient")
    self.coefficients: list[float] = list(coefficients)

  def degree(self) -> int:
    """
      The highest power with a non-zero coefficient (0 for a constant).\n
    """
    # walk powers high-to-low for the first non-zero coefficient.
    for power in range(len(self.coefficients) - 1, -1, -1):
      if self.coefficients[power] != 0:
        return power
    return 0

  def leading_coefficient(self) -> float:
    """
      The coefficient on the highest non-zero power — the `a_k` the\n
      theorem requires to be positive for the Theta(n^k) conclusion.\n
    """
    return self.coefficients[self.degree()]

  def evaluate(self, size: int) -> float:
    """
      The value of the polynomial at n = `size`, by Horner's rule.\n
    """
    # fold high power down, each step multiplying by size and adding a_i.
    total: float = 0.0
    for coefficient in reversed(self.coefficients):
      total = total * size + coefficient

    return total

  def growth_exponent(self) -> int:
    """
      The exponent k such that this polynomial is Theta(n^k).\n
      That is exactly its degree, provided the leading coefficient is\n
      positive (otherwise the "Theta(n^k)" conclusion does not apply).\n
    """
    if self.leading_coefficient() <= 0:
      raise ValueError("Theta(n^k) needs a positive leading coefficient")
    return self.degree()

  def upper_bound_witness(self) -> BoundWitness:
    """
      A (c, n0) witness for f(n) = O(n^degree), built by the lesson's\n
      method: for n >= 1 every lower power is at most n^degree, so summing\n
      the absolute values of all coefficients bounds f(n) by\n
      (sum |a_i|) * n^degree. Hence c = sum of |a_i| and n0 = 1.\n
    """
    constant: float = sum(abs(coefficient) for coefficient in self.coefficients)
    return BoundWitness(constant=constant, threshold=1)

$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) \leq 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) \geq ∣ S ∣ = (2 n) = \frac{n ( n - 1 )}{2} = \frac{n ^{2}}{2} - \frac{n}{2} .

This forces $T (n) \neq = O (n^{1.9})$ ; indeed $\frac{n ^{2}}{2} - \frac{n}{2} \neq = 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 > (2 c)^{10}$ . The moral: $O$ alone tells you the cost is no worse than something; only matching it with $Ω$ (i.e. proving $Θ$ ) certifies you have found the true growth rate.

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

Valid bounds for exchange sort's

Θ (n^{2})

cost, by exponent. Every

O (n^{k})

with

k \geq 2

holds but only

k = 2

is tight;

Ω (n^{2})

rules out the whole region below

k = 2

. The bounds pinch shut exactly at

Θ (n^{2})

Little-o and little-omega: strict bounds

$O$ and $Ω$ 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$ ( $n = o (n^{2})$ , $log n = o (n)$ ), and $f = ω (g)$ means $f$ dominates $g$ ( $n^{2} = ω (n)$ , $n = ω (log n)$ ) — mirror images, since $f = o (g) \leftrightarrow g = ω (f)$ . A useful analogy from CLRS: $O, Ω, Θ, o, ω$ are to functions as $\leq, \geq, =, <, >$ are to numbers.

Each asymptotic notation mirrors a comparison on numbers:

o, O, Θ, Ω, ω

line up with

<, \leq, =, \geq, >

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

2 n = O (n)

3 n^{2} = Θ (n^{2})

n^{2} = Ω (n)

2^{n} = ω (n^{2})

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 $ω (g) \subseteq Ω (g)$ . The containment is proper, and the counterexample is as small as they come:

The picture to hold: $o (g)$ is the part of $O (g)$ that keeps a widening gap below $g$ , and $Θ (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 $Ω (g)$ bound, and hence no $Θ (g)$ bound, can hold. The sets $o (g)$ , $Θ (g)$ , and $ω (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 $Ω (n)$ , and the pair cannot be ranked at all.³ 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.

asymptotic_relation.pypython

import math
from enum import Enum, auto
from typing import Callable

# A growth function maps an input size to a non-negative cost.
GrowthFunction = Callable[[int], float]

class Relation(Enum):
  """
    The strict verdict of comparing f to g by the limit of the ratio.\n
    LITTLE_O is f = o(g) (so also f = O(g)); THETA is f = Theta(g);\n
    LITTLE_OMEGA is f = omega(g) (so also f = Omega(g)). These mirror\n
    <, =, > on numbers.\n
  """
  LITTLE_O = auto()
  THETA = auto()
  LITTLE_OMEGA = auto()

def limit_of_ratio(
  numerator: GrowthFunction,
  denominator: GrowthFunction,
  largest_size: int = 1 << 14,
) -> float:
  """
    Estimate lim_{n->inf} numerator(n) / denominator(n) by probing the\n
    ratio at geometrically growing sizes up to `largest_size`. Returns\n
    math.inf when the ratio is diverging and 0.0 when it is vanishing.\n
    The verdict comes from the *trend* of the last two probes, not their\n
    raw magnitude: a ratio still shrinking by a factor of two each\n
    doubling is heading to 0, one still growing is heading to infinity,\n
    and one that has settled is a finite constant. `denominator` must be\n
    eventually positive.\n
  """
  # probe the ratio at doubling sizes, keeping the last two readings.
  size: int = 1
  previous: float = 0.0
  current: float = 0.0
  while size <= largest_size:
    bottom: float = denominator(size)
    if bottom > 0:
      previous = current
      current = numerator(size) / bottom
    size *= 2

  # an outright vanishing or diverging final ratio settles it on its own.
  if current == 0.0:
    return 0.0
  if math.isinf(current):
    return math.inf

  # read the trailing trend: flat -> constant, shrinking -> 0, growing -> inf.
  if previous <= 0.0:
    return current
  trend: float = current / previous
  if trend < 0.95:
    return 0.0
  if trend > 1.05:
    return math.inf

  return current

def classify(
  numerator: GrowthFunction,
  denominator: GrowthFunction,
  largest_size: int = 1 << 14,
) -> Relation:
  """
    The strict relation of `numerator` to `denominator` from the limit of\n
    the ratio: 0 -> LITTLE_O, a finite positive constant -> THETA,\n
    infinity -> LITTLE_OMEGA.\n
  """
  ratio: float = limit_of_ratio(numerator, denominator, largest_size)
  if ratio == 0.0:
    return Relation.LITTLE_O
  if math.isinf(ratio):
    return Relation.LITTLE_OMEGA
  return Relation.THETA

def is_big_o(
  numerator: GrowthFunction,
  denominator: GrowthFunction,
  largest_size: int = 1 << 14,
) -> bool:
  """
    Whether numerator = O(denominator): the loose upper bound, true when\n
    the relation is LITTLE_O or THETA (since o and Theta both imply O).\n
  """
  return classify(numerator, denominator, largest_size) in (
    Relation.LITTLE_O,
    Relation.THETA,
  )

def is_big_omega(
  numerator: GrowthFunction,
  denominator: GrowthFunction,
  largest_size: int = 1 << 14,
) -> bool:
  """
    Whether numerator = Omega(denominator): the loose lower bound, true\n
    when the relation is LITTLE_OMEGA or THETA.\n
  """
  return classify(numerator, denominator, largest_size) in (
    Relation.LITTLE_OMEGA,
    Relation.THETA,
  )

def is_big_theta(
  numerator: GrowthFunction,
  denominator: GrowthFunction,
  largest_size: int = 1 << 14,
) -> bool:
  """
    Whether numerator = Theta(denominator) — a tight, two-sided bound,\n
    equivalently both O and Omega.\n
  """
  return classify(numerator, denominator, largest_size) is Relation.THETA

def witnesses_big_o(
  numerator: GrowthFunction,
  denominator: GrowthFunction,
  constant: float,
  threshold: int,
  largest_size: int = 1 << 14,
) -> bool:
  """
    Check a concrete O-bound witness against the definition: whether\n
    numerator(n) <= constant * denominator(n) holds for every probed\n
    n >= `threshold`. This is the exact inequality an O proof claims, with\n
    the candidate `constant` (c) and `threshold` (n0) supplied.\n
  """
  if constant <= 0 or threshold <= 0:
    raise ValueError("a witness needs c > 0 and n0 > 0")

  # test the inequality from n0 up, densely near n0 then doubling.
  size: int = threshold
  while size <= largest_size:
    if numerator(size) > constant * denominator(size):
      return False
    size += 1 if size < threshold + 64 else size

  return True

Comparing functions with limits

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

n \to \infty lim \frac{f ( n )}{g ( n )} = ⎩ ⎨ ⎧ 0 c \in (0, \infty) \infty \Rightarrow f = o (g) (so also f = O (g)) \Rightarrow f = Θ (g) \Rightarrow f = ω (g) (so also f = Ω (g)) .

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 = Θ (g)

; a ratio climbing without bound certifies

f = ω (g)

One caution. The test is sufficient, not necessary: the limit may fail to exist even when a $Θ$ -bound holds. The function $f (n) = (2 + (- 1)^{n}) n$ hops between $n$ and $3 n$ forever, so $f (n) / n$ has no limit, yet $f = Θ (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.⁴

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

x \to \infty lim \frac{ln x}{x ^{0.1}} = x \to \infty lim \frac{1/ x}{0.1 x ^{- 0.9}} = x \to \infty lim \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 $1 0^{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.⁵ 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}} .

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

n^{a}

becomes

m^{b}

2^{am}

, and the exponential wins.

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 (1 - \frac{b}{a} \cdot \frac{log _{2} m}{m}) ⟶ - \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 ⟶ - \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} = ω (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 $1 6^{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.

Small inputs lie. The vertical axis is the ratio of

log^{4} n

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.

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} = Θ (log_{2} n) for every constant b > 1.

So $log_{2} n$ , $log_{10} n$ , and $ln n$ all live in the same $Θ$ -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 $Ω$ 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:⁶

log (ab) = log a + log b, log (a^{b}) = b log a, 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 \dots 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 = Θ (log n)$ : the logarithm of any polynomial in $n$ is just $Θ (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:

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 and would otherwise be hard to place in the hierarchy.

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

Stirling's approximation sharpens the same statement to $log (n!) = n log n - Θ (n)$ ,⁷ 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 that do $Θ (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.

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, $Ω$ a lower bound, $Θ$ a tight (two-sided) bound; $o$ and $ω$ are their strict versions. $f = Θ (g) \leftrightarrow f = O (g)$ and $f = Ω (g)$ .
$O$ alone certifies only that the cost is no worse than something; matching it with $Ω$ (proving $Θ$ ) 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$ , $Θ$ , or $ω$ . 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 $1 0^{17}$ ; only the limit verdict is final.
Logarithms: the base never matters inside $Θ$ ; $log$ turns products into sums; $a^{log_{b} c} = c^{log_{b} a}$ turns exponentials in $log n$ into plain polynomials; and $log (n!) = Θ (n log n)$ by the half-the-terms trick.

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

The RAM model of computation

From problem to T(n)

Worst, average, and best case

Why we drop constants and lower-order terms

The asymptotic notations

Big-O: asymptotic upper bound

Big-Omega: asymptotic lower bound

Big-Theta: asymptotic tight bound

The polynomial theorem

O is an upper bound, not a promise of tightness

Little-o and little-omega: strict bounds

Strict implies loose, never the reverse

Comparing functions with limits

The ratio test, worked three times

Small inputs lie

The logarithm identities analysis leans on

Takeaways

Footnotes

From problem to $T (n)$

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