Big-O in practice

Two programs can give the same answer while one finishes in a blink and the other runs for an hour. The computer isn't the difference. What matters is how the work grows as the input grows: with 10 values both are instant, with a million values only one of them is.

You could time a program with a clock, but the time changes from computer to computer and with whatever else the computer is doing. Counting steps doesn't. Here three functions count how many times their innermost line runs:

def one_loop(n):
    steps = 0
    for i in range(n):
        steps += 1
    return steps


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


def halving(n):
    steps = 0
    while n > 1:
        n = n // 2
        steps += 1
    return steps


for n in [10, 100, 1000]:
    print(n, one_loop(n), every_pair(n), halving(n))

10 10 45 3
100 100 4950 6
1000 1000 499500 9

Read the columns down. one_loop grows with n: ten times the input, ten times the work. every_pair meets each pair of values once, n × (n - 1) / 2 steps: ten times the input, about a hundred times the work. halving halves n until 1 is left, so ten times the input adds only about three steps.

Big-O

Big-O notation names that growth and leaves out the details. one_loop is O(n), every_pair is O(n²) and halving is O(log n). Two more come up all the time: O(1), the same work whatever the size, and O(n log n), the cost of sorting.

Big-O drops constant factors: every_pair does about n²/2 steps, and that is still O(n²). Two loops one after the other do 2n steps, still O(n). For big inputs, the growth beats any constant. Plain Python does roughly ten to fifty million simple steps a second, so an O(n²) loop over 200,000 values, 20 billion steps, runs for many minutes, while an O(n) loop over them takes a fraction of a second.

Loops you don't see

A line can be a loop in disguise. x in values on a list, values.index(x), values.count(x), values.remove(x), max(values) and sum(values) go through the items one by one: O(n) each. A slice values[a:b] copies its items, and values.pop(0) or values.insert(0, x) moves every other item by one place. Put one of them in a loop over the list and you have O(n²) without a second for. (To take items from the front again and again, use a collections.deque, the queue of the module on trees: it removes its first item in O(1).)

These two functions find the best profit from buying on one day and selling on a later day. Both are right:

def best_profit_slow(prices):
    best = 0
    for i in range(len(prices) - 1):
        best = max(best, max(prices[i + 1:]) - prices[i])
    return best


def best_profit(prices):
    best = 0
    lowest = prices[0]
    for price in prices:
        lowest = min(lowest, price)
        best = max(best, price - lowest)
    return best


prices = [9, 11, 8, 5, 7, 10, 6]
print(best_profit_slow(prices))
print(best_profit(prices))

5
5

best_profit_slow has one for, but max(prices[i + 1:]) copies and scans the rest of the list in every round: O(n²) in all. best_profit remembers the lowest price so far instead, so each round is O(1): the function is O(n) time, with O(1) extra memory (two variables, whatever the length of the list). Remembering something as you go is the most common way to remove a hidden loop.

Sorting first

Sorting costs O(n log n), and it often pays: after sorting, equal and close values sit next to each other. To find out whether a list has a repeated value, comparing every pair is O(n²). In a sorted list, a repeated value sits right next to its twin, so one pass over the neighbors is enough: O(n log n) for the sort plus O(n) for the pass, O(n log n) in all.

def has_repeat(values):
    ordered = sorted(values)
    for i in range(len(ordered) - 1):
        if ordered[i] == ordered[i + 1]:
            return True
    return False


print(has_repeat([31, 7, 19, 7, 2]))
print(has_repeat([31, 7, 19, 8, 2]))

True
False

sorted makes a new sorted list, O(n) extra memory, and leaves the original as it was.