Big-O: how the work grows with n

You need to find a name in a sorted list of 1,000. One way checks each name in turn: up to 1,000 looks. Another opens the list in the middle, sees which half the name is in, and repeats: at most 10 looks. Make the list a million names long and the first way needs up to a million looks, the second about 20.

A stopwatch can't settle which is faster: it depends on the machine, the language and the list you happened to try. What doesn't change is how the number of steps grows as the input grows. Big-O is the name for that growth.

n

The size of the input: the items in a list, the nodes in a graph, the characters in a string.

step

One basic operation the algorithm repeats, such as a comparison, a swap or a probe. We count these, not seconds.

growth

How the step count changes as n grows. The quickest test: double n and see what happens to the count.

O(f(n))

For large enough n, the steps are at most a constant times f(n). Constant factors and smaller terms are dropped.

worst case

The input of size n that takes the most steps. A Big-O without a qualifier usually means this one.

Bubble sort compares neighbours and swaps them, pass after pass. Merge sort splits the list in halves, sorts each half and merges them. Here is how many comparisons each makes on random lists as n goes from 4 to 64.

At n = 8 the two are close. At n = 64, bubble sort makes about 2,000 comparisons and merge sort about 310. Now try the doubling test: from n = 32 to n = 64, bubble sort's count goes up about four times, and merge sort's only a little more than twice. Bubble sort compares about every pair, roughly n²/2 of them, so it is O(n²). Merge sort does about n comparisons on each of log₂ n levels of halving, so it is O(n log n).

The classes you will meet most, from slowest-growing to fastest:

• O(1), constant: the same steps whatever n is, like reading A[i].
• O(log n), logarithmic: the problem halves every step, as in binary search. A million values take about 20 steps.
• O(n), linear: each item is looked at once, as in linear search or adding up a list.
• O(n log n): halve the problem, then do O(n) work at each of the log n levels, as merge sort does.
• O(n²), quadratic: every pair, as in bubble sort or two loops nested over the same list.

This function counts how many times its inner line runs. The inner loop starts just after i, so it visits each pair of positions once.

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

print(count_pairs(4))

Linear search checks each value in turn; binary search halves a sorted array with every probe. Both look for a value that isn't there, the worst case for each.

Linear search's line is the n line itself: double n and its probes double. Binary search's barely rises: doubling n adds one probe, because one more halving undoes the doubling. Run it yourself: try n = 7 and then n = 15 and count the probes.

• Count steps as a function of n, not seconds. Big-O names how that count grows.
• Keep the fastest-growing term and drop constants: 3n² + 50n is O(n²).
• The doubling test: constant stays put, O(log n) adds one step, O(n) doubles, O(n log n) a bit more than doubles, O(n²) quadruples.
• Loops one after another add; loops nested inside each other multiply.
• Next: recursion, where counting the calls in the call tree gives the Big-O, and arrays, where O(1) indexing and O(n) inserts come from. To race more sorts against each other, open the sorting race.