Big-O notation

Big-O describes how an algorithm's running time or memory grows with the input size, ignoring constants. It is the shared language for saying one approach scales and another does not.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

Explain what Big-O describes and why constants are dropped
Work out the Big-O of a short function with nested loops
Spot the hidden O(n) inside a library call in a loop

In practice

A few lines that show Big-O notation doing its job.

Python

def has_duplicate_slow(items):          # O(n^2)
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

def has_duplicate(items):               # O(n)
    return len(set(items)) != len(items)

The common mistake

Watch for

Counting the loops you can see and missing the ones hidden in library calls. A list.index() or "in list" inside a loop is itself O(n), which turns a loop into O(n^2).

How it stays learned

Once a session shows you understand Big-O notation, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

Day 3First recall, while it is fresh
Day 7Second, a week on
Day 18Last, when it has settled

Where it leads

Topics that build on Big-O notation.

Next in the moduleTime versus space →