lesson 171 Algorithms & Complexity · advanced

Big O: how the work grows

A program that is quick on 100 records can crawl on 100,000. Counting its basic operations as the input grows tells you which programs will, before you find out the hard way.

You'll be able to

Instrument a function with a counter to measure how many comparisons it makes
Recognise O(1), O(n) and O(n²) from how the count changes when n doubles
Tell the best case from the worst case of an algorithm that can stop early

The idea

A stopwatch says how long a program took *on this machine, today*. A count of the basic operations it performs (comparisons, lookups, additions) is the same everywhere, and it shows how the cost changes with the size of the input, which we call n.

To count, add a counter variable and increase it exactly where the operation happens. Then run the same function for n, 2n and 4n and look at how the count moves.

Run each example to see what it prints. Running examples doesn't count toward progress.

example-1.py · One loop against two nested loops

def scan_cost(n):
    items = list(range(n))
    comparisons = 0
    for item in items:
        comparisons += 1
        if item == -1:
            break
    return comparisons

def pairs_cost(n):
    comparisons = 0
    for i in range(n):
        for j in range(i + 1, n):
            comparisons += 1
    return comparisons

for n in [10, 20, 40]:
    print(n, scan_cost(n), pairs_cost(n))

Big O names that growth and ignores the details that don't change it. A scan of n items is O(n) (linear): twice the data, twice the work. Comparing every pair is O(n²) (quadratic): twice the data, four times the work. Reading items[0] or len(items) is O(1) (constant): the list's size doesn't matter. Constant factors are dropped: n·(n−1)/2 is still O(n²), because for large n the n² term is what you feel.

The same idea applies when there are two inputs. Matching every customer against every order costs one comparison per (customer, order) pair, O(n·m).

example-2.py · Orders per customer, every pair compared

def orders_per_customer(customers, orders):
    counts = {}
    comparisons = 0
    for customer in customers:
        counts[customer] = 0
        for order in orders:
            comparisons += 1
            if order["customer_id"] == customer:
                counts[customer] += 1
    return counts, comparisons

customers = ["C00038", "C00077", "C01338"]
orders = [
    {"order_id": "O100282", "customer_id": "C00077"},
    {"order_id": "O100918", "customer_id": "C01338"},
    {"order_id": "O101219", "customer_id": "C00077"},
    {"order_id": "O101723", "customer_id": "C01338"},
]
print(orders_per_customer(customers, orders))
print(orders_per_customer(customers * 2, orders * 2)[1])

When to use it: before you trust a function with real data, ask what its count does when n doubles. Loops inside loops over the same data are the usual O(n²) suspects. Mistakes to avoid: counting the wrong thing (incrementing inside the if counts matches, not comparisons); judging by one tiny input, where every algorithm looks fast; and forgetting that an early break changes the best case, not the worst. The next lessons replace the slow patterns: binary search, then hashing.

Review

Count the operation you care about every time it happens, then compare the counts at n, 2n and 4n.
O(1) stays flat, O(n) doubles, O(n²) quadruples when n doubles; constant factors are dropped.
An early stop helps the best case; the worst case decides how a program behaves on bad days.
Next: sorted data lets a search skip most of the list, with binary search and bisect.

Practise this

Merge two sorted delivery lists and count the work