Measuring efficiency: big O

Ridgeline Coffee Roasters started with six coffees, a dozen online orders a day and a stock file that fit on one screen. Jordan's PYTH-102 package handled that easily. Now Rosa is talking about wholesale accounts, a second cafe and a loyalty program with thousands of members, and Theo has started asking a new kind of question: not whether the tools give the right answer, but whether they will still give it quickly when the shop is ten or a hundred times bigger. A report that takes a second today could take a minute or an hour next year, depending on how it was written.

This course is about writing programs that stay fast as their data grows. It covers the classic data structures (lists, stacks, queues, linked lists, hash tables, trees, heaps and graphs) and the algorithms that work on them (searching, sorting and graph search). This first lesson builds the vocabulary for everything that follows: how to measure the cost of an algorithm by counting its steps, how big O notation describes the way that cost grows, and how to read a piece of code and estimate its growth rate before you ever run it.

Why speed depends on growth, not on seconds

The obvious way to compare two programs is to time them. Timing is useful, and the last section of this lesson shows how to do it properly, but on its own it misleads. A program's running time depends on the computer, on what else the computer is doing, on the version of Python and on the particular data used for the test. Two programs that both finish in a blink with 100 orders can behave completely differently with 100,000. What matters most is how the work grows as the input grows.

Computer scientists therefore describe an algorithm by counting basic steps, such as comparisons, additions or list lookups, as a function of the input size, usually called n. For Ridgeline, n might be the number of orders, coffees, customers or roast batches. We do not care whether one step takes a nanosecond or a microsecond; we care whether doubling n doubles the work, quadruples it, or barely changes it.

def count_matches(orders, sku):
    """Count orders for one SKU, and count the comparisons made."""
    steps = 0
    found = 0
    for order in orders:
        steps += 1                 # one comparison per order
        if order == sku:
            found += 1
    return found, steps

for n in [10, 100, 1000, 10000]:
    orders = ["RC-101", "RC-104", "RC-106", "RC-102", "RC-103"] * (n // 5)
    found, steps = count_matches(orders, "RC-104")
    print(f"n = {n:>6}: found {found:>5}, comparisons {steps:>6}")

n =     10: found     2, comparisons     10
n =    100: found    20, comparisons    100
n =   1000: found   200, comparisons   1000
n =  10000: found  2000, comparisons  10000

Ten times more orders means ten times more comparisons. That pattern, work proportional to n, is called linear growth, and it is the first of several growth rates you will learn to recognize.

Counting steps in a nested loop

Now consider a different question. Mei wants to know whether any two loyalty members share the same phone number, which would suggest a duplicate account. The most direct approach compares every member with every other member. That is a loop inside a loop, and the number of comparisons grows much faster.

def has_duplicate_slow(phones):
    steps = 0
    for i in range(len(phones)):
        for j in range(i + 1, len(phones)):
            steps += 1
            if phones[i] == phones[j]:
                return True, steps
    return False, steps

for n in [10, 100, 1000, 2000]:
    phones = [f"555-{k:04d}" for k in range(n)]      # no duplicates: the worst case
    dup, steps = has_duplicate_slow(phones)
    print(f"n = {n:>5}: duplicate {dup}, comparisons {steps:>9,}")

n =    10: duplicate False, comparisons        45
n =   100: duplicate False, comparisons     4,950
n =  1000: duplicate False, comparisons   499,500
n =  2000: duplicate False, comparisons 1,999,000

With 1,000 members the function makes 499,500 comparisons; doubling to 2,000 members roughly quadruples that to almost two million. The exact count is n(n - 1)/2, but the important fact is that it grows like n squared. Lesson 5 shows how a set answers the same question with about n steps, which for Ridgeline's eventual 50,000 loyalty members is the difference between 50,000 steps and over a billion.

Big O notation

Big O notation is the standard shorthand for growth rates. Saying an algorithm is O(n), read as order n or big O of n, means its work grows at most in proportion to n once n is large enough. O(n²) means the work grows at most like n squared. Formally, a function f(n) is O(g(n)) if there are constants c and n₀ such that f(n) ≤ c·g(n) for every n ≥ n₀; in practice, you find the big O by keeping the fastest-growing term and dropping constant factors.

For f(n) = 3n² + 5n + 20, the n² term dominates once n is moderately large: at n = 1,000 it contributes 3,000,000 of the 3,005,020 steps. The constant 3 depends on details such as how many operations one loop iteration really takes, and those details change with the machine and the language, so big O ignores it. Dropping lower terms and constants is not sloppiness; it is a deliberate focus on what decides whether a program scales.

The growth rates you will meet most often, from best to worst, are these:

• O(1), constant: the work does not depend on n, such as reading one item of a list by index or looking up a dictionary key.
• O(log n), logarithmic: the work grows by one step each time n doubles, such as binary search in a sorted list.
• O(n), linear: the work is proportional to n, such as one pass through a list.
• O(n log n), linearithmic: slightly more than linear, the cost of good sorting algorithms.
• O(n²), quadratic: the work grows with the square of n, typical of comparing every pair.
• O(2ⁿ), exponential: the work doubles with each extra item, such as trying every subset of a set of items.

import math

print(f"{'n':>8} {'log2 n':>8} {'n log2 n':>12} {'n squared':>15} {'2 to the n':>14}")
for n in [8, 64, 1024, 65536]:
    two_n = f"{len(str(2 ** n))} digits" if n <= 1024 else "far bigger"
    print(f"{n:>8} {math.log2(n):>8.0f} {n * math.log2(n):>12,.0f} {n * n:>15,} {two_n:>14}")

       n   log2 n     n log2 n       n squared     2 to the n
       8        3           24              64       3 digits
      64        6          384           4,096      20 digits
    1024       10       10,240       1,048,576     309 digits
   65536       16    1,048,576   4,294,967,296     far bigger

The table shows why the categories matter more than constants. An O(n log n) sort of 65,536 orders needs about a million steps; an O(n²) method needs over four billion. No faster computer rescues an exponential algorithm: 2 to the 1024 is a number with more than 300 digits.

Best, worst and average cases

The number of steps often depends on the data as well as its size. Searching a list for a coffee that happens to be first takes one comparison; searching for one that is last, or absent, takes n. Analysts therefore distinguish the best case, the worst case and the average case. Big O is usually quoted for the worst case, because it is a guarantee: whatever the input, the algorithm will not do worse.

def find_index(skus, target):
    for i, sku in enumerate(skus):
        if sku == target:
            return i, i + 1            # position and comparisons used
    return -1, len(skus)

skus = ["RC-101", "RC-102", "RC-103", "RC-104", "RC-105", "RC-106"]
for target in ["RC-101", "RC-104", "RC-106", "RC-999"]:
    pos, comps = find_index(skus, target)
    print(f"{target}: position {pos:>2}, comparisons {comps}")

RC-101: position  0, comparisons 1
RC-104: position  3, comparisons 4
RC-106: position  5, comparisons 6
RC-999: position -1, comparisons 6

If every coffee is equally likely to be the target, the average successful search makes about n/2 comparisons, which is still O(n): halving a linear cost does not change its growth rate. Average-case analysis needs an assumption about what inputs are likely, so it is less of a guarantee, but it can be more realistic. Lesson 5 explains why dictionaries are O(1) on average even though their worst case is linear.

Reading code to find its big O

With practice you can estimate the big O of most code by reading it. A few rules cover the common cases. Simple statements such as assignments, arithmetic and indexing a list are O(1). A loop that runs n times around an O(1) body is O(n). A loop nested inside another, each running n times, is O(n²). Steps in sequence add, and the larger term wins, so an O(n) loop followed by an O(n²) loop is O(n²). A loop that halves the remaining work on each pass is O(log n).

Hidden loops deserve special care. Built-in operations look like single steps but may loop internally: x in some_list scans the list (O(n)), some_list.insert(0, x) shifts every item (O(n)), sorted(items) is O(n log n), and building a string with + inside a loop can copy the growing string each time. Lesson 2 measures several of these list operations.

def halvings(n):
    """How many times can n be halved before reaching 1?"""
    count = 0
    while n > 1:
        n //= 2
        count += 1
    return count

for n in [16, 1000, 1_000_000, 1_000_000_000]:
    print(f"{n:>13,} can be halved {halvings(n):>2} times")

           16 can be halved  4 times
        1,000 can be halved  9 times
    1,000,000 can be halved 19 times
1,000,000,000 can be halved 29 times

A billion can be halved only about 30 times before reaching 1. That is why logarithmic algorithms feel almost free: binary search, which lesson 7 develops, finds any item among a billion sorted items in about 30 comparisons.

def pair_steps(n):
    return n * n

print(pair_steps(4))

Timing code honestly

Big O tells you how code scales; measurements tell you how fast it actually is on a real machine with real data. Both matter. Python's timeit module runs a small piece of code many times and reports the total time, which smooths out noise from other programs. Results vary from machine to machine and run to run, so the listing below is shown with sample output only; edit and run it to see your own numbers.

import timeit

skus = [f"RC-{k:04d}" for k in range(10_000)]
as_set = set(skus)

t_list = timeit.timeit(lambda: "RC-9999" in skus, number=200)
t_set = timeit.timeit(lambda: "RC-9999" in as_set, number=200)
print(f"list membership: {t_list:.5f} s for 200 checks")
print(f"set membership:  {t_set:.5f} s for 200 checks")

list membership: 0.01523 s for 200 checks
set membership:  0.00001 s for 200 checks

A few habits make timing trustworthy. Time realistic data sizes, and several sizes rather than one, so you can see growth. Repeat the measurement and take the best or the median. Time only the part you care about, not the set-up. And always check that a faster version still gives the same answer. In PYTH-250 you will use profilers to find which part of a large program is slow before changing anything; measuring first avoids optimizing code that was never the problem.

def growth(steps_small, steps_big):
    if steps_big == steps_small:
        return 'constant'
    return 'linear'

print(growth(100, 200))

Space complexity

Time is not the only cost. An algorithm also uses memory, and the same big O notation describes how that memory grows. Counting matches in a list needs only two counters however long the list is, so it uses O(1) extra space. Building a dictionary of totals by SKU needs one entry per distinct SKU, O(k) for k SKUs. Making a sorted copy of a list needs O(n) extra space, while sorting it in place with list.sort() needs very little.

Often you can trade one cost for the other. The set-based duplicate check in lesson 5 uses O(n) extra memory to cut the time from O(n²) to O(n). Caching, which you met with functools.lru_cache in PYTH-102, stores answers in memory to avoid recomputing them. For Ridgeline's data sizes memory is cheap and time matters more, but on very large data, such as a year of sales on a small cloud server, space becomes just as important.

import sys

counts = {}
for sku in ["RC-101", "RC-104", "RC-101", "RC-106", "RC-101"]:
    counts[sku] = counts.get(sku, 0) + 1
print(counts)

small, big = list(range(1_000)), list(range(100_000))
print(sys.getsizeof(small) < sys.getsizeof(big), len(big) // len(small))

{'RC-101': 3, 'RC-104': 1, 'RC-106': 1}
True 100