Complexity analysis cheat sheet

Big O in plain words

Big O describes how the work (or memory) grows as the input gets bigger, ignoring constant factors and smaller terms. O(n) means doubling the input roughly doubles the work; O(n²) means it roughly quadruples. It is an upper bound on growth, so it tells you how an algorithm scales, not its exact speed on small inputs.

Reading the cost of loops

Count how many times the innermost statement runs. Independent nested loops multiply: n × m. A dependent inner loop such as for j in range(i) runs 0 + 1 + … + (n - 1) = n(n - 1)/2 times, which is still O(n²). Loops one after another add, so O(n) + O(n²) is O(n²).

Where O(log n) comes from

A logarithm appears whenever each step cuts the remaining work by a constant factor. Halving n repeatedly reaches 1 after about log₂ n steps: about 20 for a million, 30 for a billion. Binary search halves the range, balanced trees halve the candidates at each level, and exponentiation by squaring halves the exponent.

Amortised cost: cheap on average, sometimes slow

Amortised cost averages over a sequence of operations in the worst case. A Python list grows its storage by a constant factor when full, so one append occasionally copies everything (O(n)), but those copies are rare enough that n appends cost O(n) in total: O(1) each, amortised. Average case is different: it averages over possible inputs, like hash lookups with random keys.

Space complexity and the call stack

Count the extra memory beyond the input: new lists, dicts, sets and queues, plus the call stack. Each pending recursive call holds a frame, so recursion uses space equal to its maximum depth: O(log n) for binary search done recursively, O(h) for a tree walk, O(n) for recursion on a list one item at a time.

What common Python operations cost

O(1) on average: list index, append and pop from the end; dict and set lookup, insert and delete; deque append and pop at both ends. O(n): x in list, list.insert(0, x), list.pop(0), slicing, list.index, copying, sum, min, max, and building a string with += in a loop. Sorting is O(n log n).

Which complexity fits which input size

Use a rough budget of about 10⁸ simple steps per second for compiled code (fewer in Python) and compare it with your complexity at the largest n. For n = 10⁵, O(n²) is 10¹⁰ steps, far over; O(n log n) is about 1.7 million, well under. Tiny limits such as n ≤ 20 hint that exponential search over subsets is expected.

Best, average and worst case

Worst case is the most work over all inputs of size n; average case is the expected work over some distribution of inputs; best case is the least. Quote the worst case by default, and add the average when it differs a lot: quicksort is O(n log n) on average but O(n²) in the worst case, and hash lookups are O(1) on average but O(n) when every key collides.

Working out the cost of recursion

Draw the call tree: cost = total work across all calls. If each call does O(1) work and makes two calls on n - 1, the tree has about 2ⁿ calls, so O(2ⁿ). If each call splits the input in half and does O(n) work to combine, there are log n levels each doing O(n) in total, so O(n log n). Memoisation caps the calls at the number of distinct arguments.

How fast can sorting be?

A comparison sort must tell apart all n! possible orders, and each comparison only has two outcomes, so it needs at least log₂(n!) ≈ n log₂ n comparisons in the worst case. Sorts that do not compare items, such as counting sort and radix sort, can run in O(n + k) when keys are small integers or fixed-length strings.

The cost of building strings

Python strings are immutable, so s += piece creates a new string and copies the old content. Repeated in a loop that is O(n²) total characters copied in the worst case. Collect the pieces in a list and call ''.join(parts) once: O(total length). CPython sometimes optimises += in place, but you should not rely on it.

The cost table for common data structures

Arrays: O(1) index, O(n) insert in the middle. Hash maps and sets: O(1) average insert, delete and lookup, no order. Binary heaps: O(1) peek at the minimum, O(log n) push and pop. Balanced search trees: O(log n) insert, delete, lookup and ordered queries. Linked lists: O(1) insert or delete at a known node, O(n) to find it.

Answer many range-total questions quickly

Build prefix sums once: prefix[i] is the total of the first i days. The total from l to r is prefix[r + 1] - prefix[l], one subtraction per query. That is O(n + q) time instead of O(n·q) for summing each range separately, and O(n) extra space.

from itertools import accumulate


def range_totals(sales: list[int],
                 queries: list[list[int]]) -> list[int]:
    prefix = [0, *accumulate(sales)]  # total of the first i days
    return [prefix[hi + 1] - prefix[lo] for lo, hi in queries]

Raise a number to a huge power, modulo m

Repeated squaring: look at the exponent's bits from lowest to highest. Keep a running answer; whenever the current bit is 1, multiply it by the current square. Square that value and shift the exponent right each step. The loop runs once per bit of exp, so it is O(log exp) multiplications with O(1) extra space, and taking mod m each time keeps the numbers small.

def power_mod(base: int, exp: int, mod: int) -> int:
    acc, sq = 1 % mod, base % mod
    while exp:
        if exp & 1:  # this bit of the exponent is set
            acc = acc * sq % mod
        sq = sq * sq % mod
        exp >>= 1
    return acc