Algorithm Analysis & Big-O

What you'll learn

To compare algorithms fairly we need a measure that doesn't depend on your laptop, the language, or the weather. That measure is Big-O: how the amount of work grows as the input grows. Master it and you can predict which algorithm wins before writing a line of code.

By the end you'll be able to:

• Explain why we measure growth, not raw seconds
• Read O, Ω, and Θ notation
• Analyze loops and recursion to find a function's complexity
• Tell best, worst, and average case apart

Why we measure growth, not seconds

Raw timings lie: a slow algorithm on a fast machine can beat a fast algorithm on a slow one — for small inputs. What we really care about is scaling: when the input doubles, does the work double, quadruple, or barely move? Big-O captures exactly that, ignoring constant factors and lower-order terms so the essential behavior stands out. Drag the slider and watch how differently each class grows:

Big-O, Big-Omega & Big-Theta

Three symbols pin down how a running time behaves as the input grows without bound:

• O(f) — an upper bound. The algorithm grows no faster than f.
• Ω(f) — a lower bound. It grows at least as fast as f.
• Θ(f) — a tight bound. It's both O(f) and Ω(f).

The complexity classes

These are the classes you'll meet again and again, from fastest-growing-slowest to catastrophic:

Analyzing code

Two rules do most of the work. Sequential steps add (and we keep the biggest); nestedloops multiply. Drop constants and lower-order terms at the end:

def first(a):          # O(1) — one step, any size
    return a[0]

def total(a):          # O(n) — one pass over n items
    s = 0
    for x in a:
        s += x
    return s

def has_dupes(a):      # O(n²) — a pair of nested loops
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] == a[j]:
                return True
    return False

first does a fixed amount of work → O(1). total touches each of n items once → O(n). has_dupes pairs every element with every later one → about n²/2 comparisons, which is O(n²). For recursion, write a recurrence and solve it — the subject of the next module.

Best, worst & average case

The same algorithm can do different amounts of work on different inputs. has_dupes returns immediately if the first two elements match (best case, O(1)) but scans everything when there are no duplicates (worst case, O(n²)). We usually quote the worst case — it's the guarantee — and sometimes the average case when the worst case is rare.

Recap & quick check

Loops are easy to analyze; recursion needs a new tool. Next up: Module 3 — Recursion, Recurrences & the Master Theorem.