Big-O: How Fast Is My Code?

Counting steps, not seconds

Different computers run at different speeds, so we don't measure code in seconds. Instead we ask: if the input gets bigger, how many more steps does my code take? The answer is written in Big-O notation. n means “the size of the input”, like the length of a list.

Think of it like this: Finding a friend's name in your phone contacts. Scrolling from the top takes longer when you have more contacts (that grows with n). Typing the first letters jumps there almost instantly.

O(1) – constant time

The same number of steps, no matter how big the input is:

def first_item(items):
    return items[0]          # one step, even for a huge list

print(first_item([7, 3, 9]))
print(first_item(list(range(1000000))))

Output

7
0

O(n) – linear time

The steps grow at the same rate as the input. Twice the data, twice the work:

def total(items):
    steps = 0
    result = 0
    for x in items:
        result += x
        steps += 1
    return result, steps

print(total([1, 2, 3, 4]))
print(total(list(range(100))))

Output

(10, 4)
(4950, 100)

O(n²) – quadratic time

A loop inside a loop. Twice the data, four times the work:

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

for n in [10, 20, 40]:
    print(n, "items ->", count_pairs(n), "steps")

Output

10 items -> 100 steps
20 items -> 400 steps
40 items -> 1600 steps

O(log n) – logarithmic time

Each step throws away half of what's left. Even huge inputs need very few steps:

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

for n in [8, 1000, 1000000]:
    print(n, "->", halvings(n), "steps")

Output

8 -> 3 steps
1000 -> 9 steps
1000000 -> 19 steps

A million items need only about 20 halvings! Binary search (Module 6) works this way.

The Big-O cheat sheet

Remember: Big-O keeps only the part that grows fastest and drops plain numbers: 3n + 5 steps is just O(n), and n² + n is just O(n²).