Complexity & Big-O

Why measure at all?

Imagine two programs that answer the same question: "does this list of user IDs contain any duplicates?" On your laptop, with 100 IDs, both finish instantly. In production, with 2 million IDs, one finishes in a third of a second and the other would run for days. Nothing about the hardware changed. The difference is entirely in how the amount of work grows as the input grows.

That growth is what complexity analysis studies. It lets you predict, before you run anything, how a program will behave on inputs far larger than the ones you tested with. It also gives you a shared vocabulary: when a colleague says "that lookup is O(n), use a set," everyone knows what they mean.

Why not just time the program? Timing is essential, and we will do plenty of it, but a stopwatch alone has three weaknesses:

• It depends on the machine. A result measured on a fast desktop says little about a Raspberry Pi or a busy server.
• It depends on the input you happened to try. A sort can be fast on already-sorted data and slow on random data.
• It does not extrapolate. Knowing a function takes 2 ms for 1,000 items tells you nothing about 1,000,000 items unless you know how it grows.

Complexity analysis answers the "how does it grow" question in a machine-independent way. Timing then confirms the analysis and supplies the constant factors that analysis deliberately ignores.

You should see the pairwise version roughly quadruple each time n doubles, while the set version roughly doubles. That ratio, not the absolute number of seconds, is the fingerprint of an algorithm's complexity. By the end of this module you will be able to predict it from the code.

Counting operations

To analyse an algorithm without a stopwatch, we count basic operations: steps that take a roughly constant amount of time regardless of input size. Examples are an arithmetic operation, a comparison, assigning a variable, indexing a list, or calling len() on a list. We do not care whether a comparison takes 3 or 30 nanoseconds; we care how many of them happen.

We also need a measure of input size, conventionally called n. For a list it is the number of elements; for a string, its length; for a number-crunching function like "is k prime?", it might be the value k itself or the number of digits in it. Always say what n means.

A worked count

def total(nums):
    s = 0                 # 1 assignment
    for x in nums:        # loop body runs n times
        s += x            # 1 addition + 1 assignment, each time
    return s              # 1 return

The count is 1 + 2n + 1 = 2n + 2. If we also count the loop's own bookkeeping (fetching the next item), maybe it is 3n + 2. The exact constant depends on what you choose to count, and that is precisely why we will soon throw constants away. What does not depend on your choices is that the count is a linear function of n: double the list, double the work.

Nested loops

def count_pairs(nums):
    count = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            count += 1
    return count

The inner loop runs n−1 times when i = 0, then n−2, and so on down to 0. The total is the sum (n−1) + (n−2) + … + 1 + 0. Pair the first and last terms, the second and second-to-last, and so on: each pair sums to n−1 and there are n/2 pairs, so the total is

n(n − 1) / 2 = ½n² − ½n

This "triangular number" shows up constantly: any time you look at every pair of items, you do about n²/2 work.

A trap in that cell: the loops do n² = 16 comparisons, but only 4 print. The cost is the 16 comparisons, not the 4 outputs. Count the work, not the visible effects.

Big-O, Big-Ω, and Big-Θ

Counts like 3n² + 5n + 2 are precise but noisy. For large n, the n² term dwarfs everything else: at n = 1,000 it contributes 3,000,000 while 5n + 2 contributes 5,002. And the leading constant 3 depends on what we decided to count. Asymptotic notation keeps only the part that matters as n grows: the dominant term, without its constant.

The intuition

• O(g), "big-O of g": the cost grows no faster than g, up to a constant factor. An upper bound.
• Ω(g), "big-Omega of g": the cost grows at least as fast as g. A lower bound.
• Θ(g), "big-Theta of g": both at once. The cost grows exactly like g, up to constants. A tight bound.

The formal definitions

Let f(n) be the cost and g(n) a simple comparison function like n².

• f ∈ O(g) if there exist constants c > 0 and n₀ such that f(n) ≤ c·g(n) for every n ≥ n₀.
• f ∈ Ω(g) if there exist constants c > 0 and n₀ such that f(n) ≥ c·g(n) for every n ≥ n₀.
• f ∈ Θ(g) if f ∈ O(g) and f ∈ Ω(g).

In words: "eventually (past n₀), f stays below some fixed multiple of g." The constant c is what lets us ignore leading coefficients; the threshold n₀ is what lets us ignore small inputs where lower-order terms still matter.

A proof you can follow

Claim: 3n² + 5n + 2 ∈ Θ(n²).

• Upper bound. For n ≥ 1 we have 5n ≤ 5n² and 2 ≤ 2n². So 3n² + 5n + 2 ≤ 3n² + 5n² + 2n² = 10n². Choose c = 10, n₀ = 1. Done: it is O(n²).
• Lower bound. For n ≥ 1, 3n² + 5n + 2 ≥ 3n². Choose c = 3, n₀ = 1. It is Ω(n²).

Both hold, so it is Θ(n²). The same argument works for any polynomial: a polynomial is Θ of its highest-degree term.

How people actually use the words

Technically O is only an upper bound, so a linear function is also O(n²) and O(2ⁿ) (both are true and useless). In practice, engineers say "O(n)" when they mean the tight bound Θ(n). That is fine in conversation, but know the difference: in an interview or paper, "this algorithm is Ω(n log n)" is a strong claim about a lower bound, while "O(n log n)" only promises it is no worse.

Rules for simplifying

• Drop constant factors: 7n ∈ Θ(n); n/2 ∈ Θ(n).
• Keep only the dominant term: n² + n log n + 1000 ∈ Θ(n²).
• Sequential steps add: an O(n) step followed by an O(n²) step is O(n + n²) = O(n²).
• Nested steps multiply: doing O(n) work for each of n items is O(n·n) = O(n²).
• Different inputs keep different letters: a loop over list a nested in a loop over list b is O(a·b), not O(n²).

The common growth classes

A handful of functions describe almost every algorithm you will meet. Listed from fastest to slowest:

Play with the visualizer below. Toggle classes on and off and increase the maximum n. Notice how the ordering is fixed once n is large enough, even if a "slow" class looks competitive for small n.

A useful rule of thumb for pure Python: about 10⁷ simple operations per second. So an O(n²) algorithm is fine up to n ≈ 3,000 for an interactive response, and an O(n log n) one handles millions. Compiled libraries like NumPy are 10–100× faster per operation, but they do not change the class.

Logarithms from scratch

Logarithms scare people, but in computing they answer one friendly question:

How many times can I halve n before I reach 1?

Start with 16: 16 → 8 → 4 → 2 → 1. Four halvings, so log₂ 16 = 4. Equivalently, 2⁴ = 16: the logarithm is the inverse of exponentiation. log₂ n = k means 2^k = n.

Why logarithms are so slow-growing

Doubling n adds just one to log₂ n. A million is about 2²⁰, so log₂ 10⁶ ≈ 20. A billion is about 2³⁰, so log₂ 10⁹ ≈ 30. Binary search through a sorted list of a billion items needs at most about 30 comparisons. That is the power of halving.

Which base?

Computer scientists usually mean base 2, mathematicians base e, engineers base 10. For Big-O it does not matter: the change-of-base rule says log_a n = log_b n / log_b a, and 1 / log_b a is just a constant factor, which Big-O drops. So we write O(log n) without a base.

Useful identities

• log(a·b) = log a + log b, so log(n²) = 2 log n ∈ O(log n).
• log(2ⁿ) = n, so halving-based and doubling-based processes are mirror images.
• In Python, n.bit_length() is ⌊log₂ n⌋ + 1 for positive integers, an exact integer logarithm.

Analysing loops and recursion

Loop patterns

The function prints [3, 1, 2], but the real lesson is its cost: x not in out scans out, which can grow to n items, so the whole thing is O(n²) in the worst case (all distinct). Replacing out membership with a set makes it O(n).

Recursion and recurrences

For recursive functions we write a recurrence: an equation that defines the cost T(n) in terms of the cost on smaller inputs.

def length(items):            # T(n) = T(n - 1) + c
    if not items:
        return 0
    return 1 + length(items[1:])  # careful: the slice itself costs O(n)!

Ignoring the slice, each call does constant work and recurses on n − 1 items: T(n) = T(n−1) + c. Unrolling: T(n) = c + c + … + c (n times) = O(n). But the slice items[1:] copies n−1 items, so the true recurrence is T(n) = T(n−1) + cn, which sums to the triangular number: O(n²). Recursion with slicing is a classic accidental quadratic.

Four recurrences worth memorising

The third one deserves a picture. Merge sort splits the list in half, sorts each half recursively, then merges in linear time. Draw the calls as a tree: the top level does n work merging; the next level has two calls doing n/2 each, still n total; and so on. There are log₂ n levels, each doing n work.

The general tool for divide-and-conquer recurrences is the Master Theorem; you will meet it properly in M28 Recursion. For now, the four rows above and the tree method cover most of what you will see.

Each step of 5 multiplies the calls by about 11 (that is φ⁵, where φ ≈ 1.618 is the golden ratio). The exact class is Θ(φⁿ), which is exponential. Memoisation, covered in M32, cuts it to O(n).

Best, worst, and average case

The same algorithm can cost very different amounts on different inputs of the same size. Consider linear search:

def find(items, target):
    for i, x in enumerate(items):
        if x == target:
            return i
    return -1

• Best case: the target is first. One comparison: Θ(1).
• Worst case: the target is last or missing. n comparisons: Θ(n).
• Average case: if the target is present and equally likely to be anywhere, the expected number of comparisons is (1 + 2 + … + n)/n = (n+1)/2: still Θ(n).

Best case is rarely useful (every algorithm is fast on some lucky input). Worst case is the default when someone quotes a Big-O without qualification, because it is a guarantee. Average case matters when worst cases are rare, and it always needs an assumption about the input distribution.

Hash tables are the classic example where the cases diverge sharply: a dict lookup is O(1) on average but O(n) in the pathological worst case where every key collides. You will see why in M23. Quicksort is another: O(n log n) on average, O(n²) in the worst case.

Amortized analysis

Python's list.append is usually described as O(1). But a list is a contiguous block of memory, and when that block is full, appending means allocating a bigger block and copying every element across: O(n). How can both be true?

The answer is amortized cost: the total cost of a long sequence of operations, divided by the number of operations. Occasional expensive steps are fine if they are rare enough that their cost, spread over the cheap steps around them, stays constant per operation.

The doubling argument

Suppose the capacity doubles whenever it fills: 1, 2, 4, 8, 16, … To append n items we copy 1 item, then 2, then 4, … up to at most n. The total copying is 1 + 2 + 4 + … + n < 2n (a geometric series where each term is bigger than all previous terms combined). Add the n writes themselves and the whole sequence costs under 3n. Divided by n appends: fewer than 3 operations each. Amortized O(1).

The key is multiplicative growth. If the list instead grew by a fixed 10 slots each time, the copies would be 10 + 20 + 30 + … ≈ n²/20: amortized O(n) per append. CPython grows by roughly 1.125× plus a small constant; any factor greater than 1 gives amortized O(1), and a smaller factor trades a little more copying for less wasted memory.

Try both growth factors in the visualizer and watch the "total copies ÷ appends" ratio settle near a constant:

The size only jumps occasionally: those are the reallocations. Between them, appends write into pre-reserved slots. You will build this mechanism yourself in M20.

Space complexity

Memory is a resource too. Space complexity measures how much extra memory an algorithm needs as a function of n, usually excluding the input itself (called auxiliary space).

• sum(nums) keeps one running total: O(1) extra space.
• sorted(nums) builds a new list: O(n) extra space. nums.sort() sorts in place, but Timsort still uses up to O(n) temporary space for merging.
• A recursive function with depth d uses O(d) stack space, one frame per active call. Python's default recursion limit (about 1000 frames) is there to protect the C stack.
• Building a set of seen items to detect duplicates is O(n) space: we bought O(n) time by spending O(n) memory.

That last point is the most common trade-off in all of data structures: spend memory to save time. Caches, indexes, hash tables, and memoisation are all versions of it.

sys.getsizeof on a list reports only the pointer array, not the integers it points to, so the true footprint is even larger. The generator from M14 uses O(1) space no matter how large the range.

Measuring: timeit, perf_counter, and plots

Analysis predicts; measurement verifies. Python gives you two main tools.

time.perf_counter()

A high-resolution, monotonic clock (it never jumps backwards when the system clock is adjusted). Call it before and after the code, subtract. Good for timing larger chunks of work once.

timeit

For small snippets, a single measurement is dominated by noise. timeit runs the code many times, turns off garbage collection during timing, and reports the total. timeit.repeat does that several times so you can take the minimum, which is the run least disturbed by other processes.

pixi run python -m timeit -s "d = list(range(10_000))" "9_999 in d"
pixi run python -m timeit -s "d = set(range(10_000))" "9_999 in d"

Plotting growth

The most convincing evidence is a plot of time against n. Even better is a log-log plot: if t ≈ c·n^k, then log t = log c + k·log n, a straight line whose slope is the exponent k. Slope 1 means linear, slope 2 means quadratic.

What Python's built-ins cost

Knowing these by heart is one of the highest-value things in this module. Here, n is the container size and k the size of the argument or slice. "Avg" means average case for hash-based structures.

A printable version lives in the complexity cheatsheet, and the official source is the Python wiki's TimeComplexity page.

Big-O isn't everything

Big-O deliberately throws information away. Sometimes that information is what decides real performance.

• Constants matter at realistic sizes. An O(n) Python loop can lose to an O(n log n) call to sorted(), which runs in C, for all n you will ever see. Insertion sort (O(n²)) beats merge sort for tiny arrays, which is why Timsort uses it for short runs.
• Memory locality and caches. Modern CPUs fetch memory in cache lines (typically 64 bytes) and are much faster at reading contiguous memory than at chasing pointers scattered around the heap. Arrays exploit this; linked lists fight it. Two O(n) traversals can differ by 10× because of caching. You will see this in M21.
• Small n. If n is always under 50, the simplest correct code usually wins. Optimise what you measure, not what you fear.
• Worst cases can be attacked. If an attacker controls your input, average-case guarantees can be weaponised; this is why Python randomises string hashing (see M23).
• Interpreter overhead. In CPython every bytecode instruction has overhead. Pushing a loop into a built-in (sum, max, comprehensions, str.join) or into NumPy is often a big constant-factor win without changing the class.

Practice

for i in range(n):
    for j in range(i):
        ...  # count this

def count_steps(n):
    count = 0
    for i in range(n):
        for j in range(i):
            count += 1
    return count

def formula(n):
    return n * (n - 1) // 2

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

def unique_in_order(items):
    out = []
    for x in items:
        if x not in out:
            out.append(x)
    return out

def unique_in_order(items):
    seen = set()
    out = []
    for x in items:
        if x not in seen:
            seen.add(x)
            out.append(x)
    return out

def copies_for(n, growth):
    capacity = 1
    size = 0
    copies = 0
    for _ in range(n):
        if size == capacity:
            copies += size
            capacity = max(capacity + 1, int(capacity * growth))
        size += 1
    return copies

import math

def guess_class(sizes, times):
    k = math.log(times[-1] / times[0]) / math.log(sizes[-1] / sizes[0])
    k = max(0, min(3, round(k)))
    return ["O(1)", "O(n)", "O(n^2)", "O(n^3)"][k]

Mini-project: an empirical complexity lab

pixi init complexity-lab
cd complexity-lab
pixi add python=3.14 matplotlib
pixi run python complexity_lab.py

Quiz

Recap

• Complexity describes how cost grows with input size n; timing confirms it and supplies constants.
• Count basic operations; drop constants and lower-order terms. Sequential costs add, nested costs multiply.
• O is an upper bound, Ω a lower bound, Θ a tight bound. Everyday "O(n)" usually means Θ(n).
• 1 < log n < n < n log n < n² < n³ < 2ⁿ < n!. A logarithm counts halvings.
• For recursion, write a recurrence; the tree method (levels × work per level) solves most of them.
• Worst case is the default. Average case needs an input assumption. Amortized bounds a whole sequence.
• Space complexity counts extra memory, including recursion depth.
• Measure with timeit or perf_counter; on a log-log plot, the slope is the exponent.
• Know the built-in costs: list front operations and in are O(n); dict and set lookups are O(1) average.
• Big-O is not everything: constants, caches, and small n matter.

Going further

• Python wiki: TimeComplexity for the costs of built-in operations.
• timeit and time.perf_counter documentation.
• Complexity cheatsheet in this course.
• Next: M20 Arrays & Dynamic Arrays, where you build the dynamic array whose amortized cost you just analysed.