Big O Notation Explained Simply (With Python Examples)

Big O notation describes how the work an algorithm does grows as its input grows. It does not measure seconds, which depend on the computer. It answers a simpler, more useful question: if the input gets 10 times bigger, roughly how much more work is there?

We write the input size as n: the number of items in a list, characters in a string, nodes in a graph.

The common growth rates#

Here is how many steps each one means for a few input sizes:

import math

print(f"{'n':>6} {'log n':>6} {'n log n':>8} {'n^2':>10} {'2^n':>22}")
for n in [10, 20, 30, 1000]:
    two_n = 2 ** n if n <= 64 else "too big to write"
    print(f"{n:>6} {round(math.log2(n)):>6} {round(n * math.log2(n)):>8} {n * n:>10} {two_n:>22}")

     n  log n  n log n        n^2                    2^n
    10      3       33        100                   1024
    20      4       86        400                1048576
    30      5      147        900             1073741824
  1000     10     9966    1000000       too big to write

At n = 1000, a logarithmic algorithm needs about 10 steps and a quadratic one a million. An exponential one needs a number with 302 digits, far more than any computer could ever finish.

Seeing the difference#

Each function below counts its own steps instead of timing them, so the result is the same on every machine:

def constant(items):
    return 1                      # one step, whatever the size

def linear(items):
    steps = 0
    for _ in items:
        steps += 1
    return steps

def quadratic(items):
    steps = 0
    for _ in items:
        for _ in items:
            steps += 1
    return steps

def logarithmic(items):
    steps, size = 0, len(items)
    while size > 1:               # halve the problem each time
        size //= 2
        steps += 1
    return steps

for n in [8, 64, 512]:
    data = list(range(n))
    print(n, constant(data), logarithmic(data), linear(data), quadratic(data))

8 1 3 8 64
64 1 6 64 4096
512 1 9 512 262144

Multiplying n by 8 adds 3 steps to the logarithmic function, multiplies the linear one by 8, and multiplies the quadratic one by 64.

Simplifying Big O#

Big O keeps only what matters for large n. Two rules do most of the work.

1. Drop constants. A loop that does 3 steps per item is O(3n), which we write as O(n). Doubling n still doubles the work; the 3 does not change the shape.

2. Keep only the biggest term. O(n² + n + 100) becomes O(n²). When n is a million, n² is a trillion and the + n is a rounding error:

n = 1_000_000
print(n * n)
print(n * n + n + 100)
print(f"{(n + 100) / (n * n + n + 100):.10%} of the total comes from n + 100")

1000000000000
1000001000100
0.0001000099% of the total comes from n + 100

Different inputs keep different letters: looping over a list of size n and then a list of size m is O(n + m), not O(n).

Best, average and worst case#

The same algorithm can take different amounts of work on different inputs. Searching a list for a value:

• best case: it is the first item, O(1);
• worst case: it is the last item or missing, O(n);
• average case: about halfway, n/2 steps, which is still O(n).

Unless someone says otherwise, Big O normally means the worst case: a guarantee that the algorithm never does worse.

Common mistakes#

Practice#

def a(items):
    return items[0] + items[-1]

def b(items):
    total = 0
    for x in items:
        total += x
    for x in items:
        total -= 1
    return total

def c(items):
    pairs = 0
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            pairs += 1
    return pairs

def c(items):
    pairs = 0
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            pairs += 1
    return pairs

for n in [10, 100, 1000]:
    print(n, c(range(n)), n * (n - 1) // 2)

10 45 45
100 4950 4950
1000 499500 499500

Key takeaway#

Next, apply these rules to real code in Analysing Time Complexity.