03Module · Goodrich Ch. 3

Week 3 — Algorithm Analysis

The seven core functions, asymptotic Big-Oh / Omega / Theta notation, justification techniques, and loop invariants.

Measuring algorithm efficiency by how cost grows with input size, and proving bounds with induction and invariants.

Theory

Experimental measurement is necessary but insufficient: results depend on hardware and inputs. Asymptotic analysis abstracts these away.

Big-O is an upper bound, Big-Omega a lower bound, and Big-Theta a tight bound on a function's growth rate.

The seven canonical functions: constant, logarithmic, linear, n log n, quadratic, cubic, exponential.

Correctness proofs use loop invariants (initialization, maintenance, termination) and induction on input size.

Key points

Drop constants and lower-order terms: 3n² + 100n + 5 is Θ(n²).
log n grows slower than nᵉ for any ε > 0.
Amortized analysis bounds the average cost of a sequence of operations.

Code examples

Three algorithms for prefix averages

# O(n^2) — recompute each prefix sum
def prefix_avg_quadratic(s):
    n = len(s)
    a = [0] * n
    for j in range(n):
        a[j] = sum(s[: j + 1]) / (j + 1)
    return a

# O(n) — running total
def prefix_avg_linear(s):
    n = len(s)
    a, total = [0] * n, 0
    for j in range(n):
        total += s[j]
        a[j] = total / (j + 1)
    return a

Loop invariant — find max

def find_max(a):
    # Invariant: best is the max of a[0:i]
    best = a[0]
    for i in range(1, len(a)):
        if a[i] > best:
            best = a[i]
    # Termination: i = len(a), so best = max(a[0:len(a)])
    return best