Data Structures · Lesson 8 of 8

Big O Notation

Worst-case growth rates and comparing algorithms.

• Intermediate
• 15 min read
• 3 objectives

Before this lessonLesson 7: Graphs

How do you compare two solutions to the same problem? Timing them on your laptop depends on the hardware and the input. Big O notation instead describes how the number of steps grows as the input size n grows. It lets you predict whether code that works on 100 items will survive 100 million.

The question Big O answers

Two programs give the same answer; which is better? Timing them on your laptop is unreliable, because it depends on the machine and the sample data. Big O notation instead describes how the work grows as the input grows. If the input doubles, does the work stay the same, double, or quadruple? That growth rate is what decides whether a program still works with a million users.

Big O ignores small details (a constant factor of 2, a lower-order term) and focuses on the shape of the growth.

The common classes

• O(1) constant: same work regardless of size. Array index, dict lookup.
• O(log n) logarithmic: each step halves the problem. Binary search.
• O(n) linear: touch every item once. Scanning a list.
• O(n log n): efficient sorting (merge sort, Python's sorted).
• O(n squared) quadratic: a loop inside a loop over the same data. Comparing all pairs.
• O(2 to the n) exponential: doubles with every added item. Naive recursion over subsets.

Reading code

def first(items):          # O(1)
    return items[0]

def total(items):          # O(n)
    s = 0
    for x in items:
        s += x
    return s

def has_pair(items):       # O(n^2)
    for i in items:
        for j in items:
            if i != j and i + j == 10:
                return True
    return False

Rules for simplifying

• Drop constants: 3n and n are both O(n). Big O describes shape, not exact counts.
• Keep the dominant term: n squared + n is O(n squared).
• Sequential steps add: an O(n) loop followed by an O(n) loop is O(n).
• Nested steps multiply: an O(n) loop containing an O(n) loop is O(n squared).

Binary search: the power of halving

On a sorted list, check the middle; the answer is in one half, so discard the other. A billion items need only about 30 comparisons.

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([1, 3, 5, 7, 9, 11], 7))

3

Space complexity

Big O also measures memory. Building a new list of n items costs O(n) extra space; swapping values in place costs O(1). Trading space for time, such as adding a hash table to avoid a nested loop, is one of the most common optimizations.

Best, average, worst

Big O usually quotes the worst case. Quicksort is O(n log n) on average but O(n squared) in the worst case; hash lookups are O(1) on average and O(n) worst case. State which one you mean.

Feel the growth

Count the operations each style of algorithm does for an input of size n. The numbers, not the notation, are what to remember.

import math

print(f"{'n':>8} {'O(log n)':>10} {'O(n)':>10} {'O(n log n)':>12} {'O(n^2)':>16}")
for n in [10, 1_000, 1_000_000]:
    print(f"{n:>8} {math.log2(n):>10.0f} {n:>10} {n * math.log2(n):>12.0f} {n * n:>16}")

       n   O(log n)       O(n)   O(n log n)           O(n^2)
      10          3         10           33              100
    1000         10       1000         9966          1000000
 1000000         20    1000000     19931569    1000000000000

At n = 1,000,000 a logarithmic algorithm does about 20 steps, a linear one a million, and a quadratic one a trillion. That is the difference between instant and never finishing.

Reading Big O straight from code

def constant(items):            # O(1): one step regardless of size
    return items[0]

def linear(items):              # O(n): one pass
    total = 0
    for x in items:
        total += x
    return total

def quadratic(items):           # O(n^2): loop inside a loop
    pairs = 0
    for a in items:
        for b in items:
            pairs += 1
    return pairs

data = list(range(100))
print(constant(data), linear(data), quadratic(data))

0 4950 10000

• No loop over the input → O(1).
• One loop over the input → O(n).
• A loop nested inside a loop over the same input → O(n^2).
• Halving the problem each step (binary search) → O(log n).
• Two loops one after the other (not nested) → still O(n); add, then drop constants.

Trade time for memory

Faster is often possible if you spend memory. Checking for duplicates with nested loops is O(n^2) time and O(1) extra space; using a set is O(n) time and O(n) space. Most real optimisations are exactly this swap.

Key takeaways

• Big O describes how work grows with input size, ignoring constants.
• Order to remember: O(1) < O(log n) < O(n) < O(n log n) < O(n^2).
• Count loops: one is linear, nested is quadratic, halving is logarithmic.
• Extra memory (a set or dict) frequently buys a big speedup.

# Write your solution here