Algorithm Analysis & Asymptotics

Before we can count operations, we need to agree on what a "step" is. Real computers have memory hierarchies, branch predictors, out-of-order execution, and dozens of other features that make precise counting impossible. Instead, we use the Random Access Machine (RAM) model, introduced by Cook and Reckhow (1973) and popularized by Knuth.

The RAM model has these properties:

• Memory: An unbounded array of cells, each holding one word. Any cell can be read or written in O(1) time (this is the "random access" part).
• Operations: Arithmetic (+, -, *, /), comparisons (<, =), and control flow (branch, jump) each take exactly one step.
• No parallelism: Steps execute one at a time.
• Word size: We assume a word is large enough to hold any index into our input (so we don't have to worry about multi-word arithmetic for pointers).

This model is deliberately simple. It ignores cache effects, branch mispredictions, and instruction-level parallelism. But it is predictive in the most important sense: an algorithm that is O(n log n) in the RAM model will outscale an O(n²) algorithm in the RAM model, and that relationship holds in practice as n grows large.

The key decision: we count primitive operations, not time in seconds. A primitive operation is one RAM step. This makes our analysis machine-independent and language-independent.

# Counting operations in a simple loop
def sum_array(A):
    total = 0          # 1 assignment = 1 op
    for i in range(len(A)):  # loop runs n times
        total += A[i]  # 1 read + 1 add + 1 write = 3 ops per iteration
    return total       # 1 op
# Total: 1 + 3n + 1 = 3n + 2 operations
# As n grows large, the '3n' term dominates.

We measure algorithmic cost as a function of input size, denoted n. But what exactly is n? It depends on the problem:

• Sorting/searching an array: n = number of elements.
• Graph algorithms: n = number of vertices, m = number of edges (two parameters).
• Integer arithmetic (primality testing): n = number of bits in the number, not its value. This is why trial division up to √N is NOT polynomial time in the input size — the number N has log₂(N) bits, so √N = 2^(n/2) is exponential.
• String algorithms: n = length of the string.

Choosing the right measure of input size is not trivial. For multiplication of two n-bit integers, the naïve grade-school algorithm is O(n²) in the bit model. Karatsuba's algorithm is O(n^1.585). This distinction only appears when you measure by bits, not by the number of "integers".

When counting operations, we ask: how many primitive RAM steps does the algorithm take as a function of n? We write this as T(n). For small, non-recursive algorithms, we can often count directly. For recursive algorithms, we set up a recurrence relation and solve it.

# T(n) analysis of linear search
def linear_search(A, target):
    for i in range(len(A)):   # i runs 0..n-1
        if A[i] == target:    # 1 comparison per iteration
            return i
    return -1

# Best case: target is at index 0 → T_best(n) = 1 comparison
# Worst case: target absent   → T_worst(n) = n comparisons
# Average case (uniform): target at random pos → T_avg(n) = (n+1)/2

We don't need the exact count T(n) — we need to know how it grows. Asymptotic notation captures growth rate by hiding constant factors and lower-order terms.

Definition (Big-O): We say f(n) = O(g(n)) if there exist positive constants c and n₀ such that for all n ≥ n₀:

f(n) ≤ c · g(n)

Intuitively: f grows no faster than g, up to a constant factor, for large enough n. Big-O is an upper bound.

Why drop constants? Because constants encode hardware speed, language overhead, and implementation details — none of which are intrinsic to the algorithm. 3n + 2 and n are both linear; they differ by a constant factor that will vary across machines.

Why drop lower-order terms? Because for large n, they become negligible. If T(n) = n² + 1000n, then for n = 1,000,000, n² = 10¹², while 1000n = 10⁹ — 1000× smaller. The lower-order term is irrelevant at scale.

Common mistake: Big-O does NOT mean "tight". T(n) = n is O(n²) by definition (just pick c = 1, and n ≤ n² for all n ≥ 1). This is technically correct but not useful. The goal is to find the tightest true upper bound.

Growth hierarchy (slowest to fastest): O(1) ⊂ O(log n) ⊂ O(√n) ⊂ O(n) ⊂ O(n log n) ⊂ O(n²) ⊂ O(n³) ⊂ O(2ⁿ) ⊂ O(n!)

# Prove: 5n^2 + 3n + 7 = O(n^2)
# We need c, n0 such that 5n^2 + 3n + 7 <= c * n^2 for all n >= n0
# For n >= 1:  3n <= 3n^2  and  7 <= 7n^2
# So: 5n^2 + 3n + 7 <= 5n^2 + 3n^2 + 7n^2 = 15n^2
# Choose c = 15, n0 = 1. QED.

# Disprove: 2^n = O(n^2)
# Suppose 2^n <= c * n^2 for all n >= n0
# Taking logs: n <= log2(c) + 2*log2(n)  -- but left grows linearly,
# right grows logarithmically: contradiction for large n.

Big-O gives an upper bound, but to characterize an algorithm precisely, we need more.

Definition (Big-Omega, Ω): f(n) = Ω(g(n)) if there exist positive constants c and n₀ such that for all n ≥ n₀:

f(n) ≥ c · g(n)

Big-Omega is a lower bound: f grows at least as fast as g.

Definition (Big-Theta, Θ): f(n) = Θ(g(n)) if f(n) = O(g(n)) AND f(n) = Ω(g(n)). Equivalently, there exist c₁, c₂, n₀ > 0 such that:

c₁ · g(n) ≤ f(n) ≤ c₂ · g(n) for all n ≥ n₀

Big-Theta is a tight bound: it characterizes the exact growth rate up to constants.

Analogy: Think of functions as runners. If f is O(g), f is never much faster than g (g is an upper pacer). If f is Ω(g), f is never much slower than g (g is a lower pacer). If f is Θ(g), f and g are pacing each other — always within a constant factor of each other.

The formal relationship: f(n) = Θ(g(n)) ⟺ lim_{n→∞} f(n)/g(n) = L for some 0 < L < ∞.

Little-o and little-ω: These are the strict versions. f(n) = o(g(n)) means lim_{n→∞} f(n)/g(n) = 0 (f is strictly dominated by g). These appear in more advanced algorithm analysis and complexity theory.

# T(n) = 3n log n + 7n + 12
# Upper bound: 3n log n + 7n + 12 <= 3n log n + 7n log n + 12 n log n
#                                   = 22 n log n   (for n >= 2)
# So T(n) = O(n log n)
#
# Lower bound: 3n log n + 7n + 12 >= 3n log n
# So T(n) = Omega(n log n)
#
# Combined: T(n) = Theta(n log n)

# Key: Theta means we can't do better AND we can't do worse
# (up to constant factors) than n log n.

Asymptotic notation describes how a function grows. But which function? An algorithm's runtime can vary on inputs of the same size n. We need to say which scenario we're analyzing.

Worst-case T_worst(n): The maximum number of operations over all inputs of size n. This is the most commonly used bound. It gives a guarantee: "no matter what input you feed me, I will finish in at most T_worst(n) steps."

For linear search: T_worst(n) = n (the target is not in the array, or is at the last position).

Best-case T_best(n): The minimum over all inputs of size n. This is rarely useful alone — it tells you nothing about typical performance. An adversary can always give you the worst input. Best-case analysis is sometimes used to prove lower bounds ("even in the best case, this algorithm must do at least X work").

Average-case T_avg(n): The expected number of operations over inputs drawn from some probability distribution, usually the uniform distribution over all size-n inputs. Average-case analysis is more realistic but harder — you must specify a distribution, and real-world inputs may not match it. Quicksort's average-case O(n log n) assumes uniformly random input; adversarial inputs achieve worst-case O(n²).

The common confusion: People often say "this algorithm is O(n)" when they mean "its worst-case runtime is O(n)." Strictly speaking, Big-O/Theta/Omega are functions describing a number, not the algorithm itself. The rigorous phrasing is: "the worst-case runtime of this algorithm is O(n)."

When algorithm textbooks (like CLRS) say "merge sort is Θ(n log n)," they mean the worst-case runtime is Θ(n log n). For insertion sort, the worst-case is Θ(n²) but the best-case (already sorted) is Θ(n).

import random

def quicksort(A, lo, hi):
    if lo < hi:
        p = partition(A, lo, hi)  # pick pivot = A[hi]
        quicksort(A, lo, p - 1)
        quicksort(A, p + 1, hi)

# Worst case: pivot always min or max element (e.g., sorted input)
#   T(n) = T(n-1) + O(n)  -->  T(n) = O(n^2)
#
# Best case: pivot always median
#   T(n) = 2T(n/2) + O(n)  -->  T(n) = O(n log n)  [Master Theorem]
#
# Average case (random permutation): O(n log n)
#   Fix by randomizing: shuffle A before calling, or choose random pivot

Recursive algorithms express their running time with a recurrence relation: T(n) = aT(n/b) + f(n), where a is the number of subproblems, n/b is the subproblem size, and f(n) is the non-recursive work.

The Master Theorem (Cormen et al.) solves this class of recurrences. Compare f(n) to n^(log_b a):

Case 1: f(n) = O(n^(log_b a − ε)) for some ε > 0 → T(n) = Θ(n^(log_b a)) (The recursive work dominates; each level multiplies the work by more than 1.)

Case 2: f(n) = Θ(n^(log_b a) · log^k n) for k ≥ 0 → T(n) = Θ(n^(log_b a) · log^(k+1) n) (The work is balanced across levels; a log factor appears.)

Case 3: f(n) = Ω(n^(log_b a + ε)) for some ε > 0, and regularity condition holds → T(n) = Θ(f(n)) (The non-recursive work dominates.)

Examples:

• Merge sort: T(n) = 2T(n/2) + Θ(n). a=2, b=2, n^(log_2 2) = n. f(n) = Θ(n) → Case 2 (k=0) → T(n) = Θ(n log n).
• Binary search: T(n) = T(n/2) + Θ(1). a=1, b=2, n^(log_2 1) = 1. f(n) = Θ(1) → Case 2 → T(n) = Θ(log n).
• Strassen matrix multiply: T(n) = 7T(n/2) + Θ(n²). n^(log_2 7) ≈ n^2.81. f(n) = O(n^2) → Case 1 → T(n) = Θ(n^2.81).

For recurrences that don't fit this form (like T(n) = T(n-1) + T(n-2) for naïve Fibonacci), use the substitution method or recursion tree method.

# Merge sort recurrence solved step by step
# T(n) = 2*T(n/2) + cn   (c is cost of merge step)
# Recursion tree: each level has total work cn
# There are log2(n) levels (tree height)
# Base cases: n leaves, each O(1)
# Total: cn * log2(n) + n*O(1) = O(n log n)

def merge_sort(A):
    if len(A) <= 1:
        return A
    mid = len(A) // 2
    L = merge_sort(A[:mid])   # T(n/2)
    R = merge_sort(A[mid:])   # T(n/2)
    return merge(L, R)        # O(n) merge

def merge(L, R):
    result, i, j = [], 0, 0
    while i < len(L) and j < len(R):
        if L[i] <= R[j]: result.append(L[i]); i += 1
        else:            result.append(R[j]); j += 1
    return result + L[i:] + R[j:]

Sometimes a data structure has occasional expensive operations but performs well on average over a sequence. Amortized analysis gives a per-operation average cost that is a genuine guarantee — not a probabilistic statement, but a worst-case guarantee on the sequence.

Example: Dynamic Array (Python list): When you append to a Python list and it's full, Python doubles the array capacity (allocates a new buffer of 2x size, copies all elements). This copy takes O(n) time. Does that mean append is O(n)?

No. Using the accounting method: think of each element as "pre-paying" 3 units of credit when inserted:

• 1 unit pays for its own insertion.
• 1 unit is saved to pay for copying itself when the array doubles.
• 1 unit is saved to pay for copying an older element.

At any doubling event (from size k to 2k), we need k copy operations. The k new elements since the last doubling have each saved 1 unit = k units total, and the k old elements have each saved 1 unit = k units total. Total saved = 2k units ≥ k copies. So every copy is already paid for! The amortized cost of append is O(1) even though individual operations can cost O(n).

Three methods for amortized analysis:

1. Aggregate method: Count the total cost of n operations, divide by n.
2. Accounting method (banker's method): Assign artificial charges to each operation; maintain non-negative "credit" balance at all times.
3. Potential method (physicist's method): Define a potential function Φ(state) ≥ 0. Amortized cost of operation i = actual cost + ΔΦ. Sum of amortized costs ≥ sum of actual costs.

Amortized analysis appears in: dynamic arrays, splay trees, Fibonacci heaps, union-find with path compression, the analysis of Dijkstra with Fibonacci heaps.

# Dynamic array: aggregate method
# n appends to an initially-empty array with doubling
# Doubling happens at sizes 1, 2, 4, 8, ..., n
# Copy costs: 1 + 2 + 4 + ... + n/2 + n
# This geometric series sums to at most 2n
# Total cost of n appends = n (actual appends) + 2n (all copies) = 3n
# Amortized cost per append = 3n / n = O(1)

class DynamicArray:
    def __init__(self):
        self.data = [None]  # capacity 1
        self.size = 0

    def append(self, val):
        if self.size == len(self.data):  # full: double
            new = [None] * (2 * len(self.data))
            for i in range(self.size):   # O(n), but amortized O(1)
                new[i] = self.data[i]
            self.data = new
        self.data[self.size] = val
        self.size += 1

Knowing the definitions is not enough — you need to be able to prove that a claimed bound is correct. There are two directions:

To prove f(n) = O(g(n)): Find explicit constants c and n₀. Common strategies:

• For polynomials: bound each term by the highest-degree term (for n ≥ 1).
• For sums of functions: bound each separately and add.
• For exponentials: use the fact that polynomials are o(exponentials).

To disprove f(n) = O(g(n)): Assume it holds and derive a contradiction. Often: take logarithms, find that the inequality eventually fails.

Limit technique: If lim_{n→∞} f(n)/g(n) = L, then:

• L = 0 → f = o(g) (and hence O(g))
• 0 < L < ∞ → f = Θ(g)
• L = ∞ → f = ω(g) (f dominates)
• L doesn't exist → use definition directly

Useful limit facts:

• log^k(n) = o(n^ε) for any k, ε > 0 (logs are slower than any polynomial)
• n^k = o(a^n) for any k > 0, a > 1 (polynomials are slower than any exponential)
• For sums: use the integral test or closed-form identities
  • Σ_{i=1}^{n} i = n(n+1)/2 = Θ(n²)
  • Σ_{i=1}^{n} i² = Θ(n³)
  • Σ_{i=1}^{n} 1/i = Θ(log n) (harmonic series)
  • Σ_{i=0}^{log n} 2^i = 2^(log n + 1) - 1 = Θ(n) (geometric series)

# Proof sketch: sum_{i=1}^{n} i = Theta(n^2)
#
# Upper bound: sum_{i=1}^{n} i <= sum_{i=1}^{n} n = n^2  -> O(n^2)
#
# Lower bound: sum_{i=1}^{n} i >= sum_{i=n/2}^{n} i
#                               >= sum_{i=n/2}^{n} (n/2)
#                               >= (n/2) * (n/2)
#                               = n^2/4  -> Omega(n^2)
#
# Therefore: Theta(n^2)

# Classic: harmonic series H(n) = 1 + 1/2 + 1/3 + ... + 1/n = Theta(log n)
# This appears in analysis of quicksort average case and BST heights
import math
def H(n): return sum(1/i for i in range(1, n+1))
# H(1000) ≈ 7.48,  math.log(1000) ≈ 6.91 -- indeed Theta(log n)