Lesson 1 of 9

Big-O: Measuring Speed

Big-O notation describes how an 's work grows as its input grows. You'll use it throughout this track to compare data structures and algorithms.

Timing code in seconds is fragile: a faster laptop changes the number, a bigger input changes it more. Big-O ignores the machine and asks one question — when the input gets 10× bigger, how much more work happens? If the work also grows 10×, that's O(n), linear. If it grows 100×, that's O(n²), quadratic. If it barely grows at all, that's O(log n) or O(1). The letter n is the input size: items in a , characters in a , users in a .


# O(1) — constant: same work no matter how big the list
def first_item(items):
    return items[0]

# O(n) — linear: touches every item once
def total(items):
    result = 0
    for x in items:          # n iterations
        result += x
    return result

# O(n²) — quadratic: for every item, loop over every item
def has_duplicate_slow(items):
    for i in range(len(items)):
        for j in range(len(items)):     # n * n comparisons
            if i != j and items[i] == items[j]:
                return True
    return False

# O(n) — same job, one pass with a set (next lessons explain why)
def has_duplicate_fast(items):
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

The common classes, fastest to slowest: O(1) constant, O(log n) logarithmic (halve the problem each step — search), O(n) linear, O(n log n) the best sorting can do in general, O(n²) quadratic (nested over the same data), O(2ⁿ) exponential (try every combination — hopeless past ~30 items). Big-O drops constants and small terms: O(2n + 5) is just O(n), because for large n the multiplier stops mattering compared to the growth shape.

Text


n = 1,000 items, 1 operation = 1 microsecond:

O(1)        1 op            instant
O(log n)    ~10 ops         instant
O(n)        1,000 ops       1 ms
O(n log n)  ~10,000 ops     10 ms
O(n^2)      1,000,000 ops   1 second
O(2^n)      way too many    longer than you can wait

Same table at n = 1,000,000:
O(n)        1 second
O(n^2)      11.5 DAYS       <- why nested loops struggle with big data

Common question

Is an O(n²) algorithm always worse than an O(n log n) one?

Big O describes how an algorithm's cost grows with the size of its input, ignoring constant factors and smaller terms. It answers the question that matters when data grows: will this still work at ten times the size? O(1) and O(log n) barely notice; O(n) keeps pace; O(n²) and worse fall over.

Use it to pick the shape of a solution (a hash map instead of a scan, a sort instead of nested comparisons) and then measure, because constants, layout and the real size of your data decide the rest. A simple algorithm that is worse on paper can be the right choice for a hundred items.

Source: Donald Knuth: "Premature optimization is the root of all evil (or at least most of it) in programming." guides your choice of algorithm; measuring decides the rest.

Common mix-ups

Each of these sounds reasonable. Think about why it is wrong, then open the explanation.

n² grows faster, so the n log n algorithm is always the better choice.
O(1) means instant.
A loop's complexity depends on how many lines it has.

Finished reading?Mark it done to track your progress.

Tip: use the ← and → keys to move between lessons.