Complexity: how to reason about cost

What big-O actually measures

Big-O is a statement about growth rate, not about speed. O(n) does not mean 'fast' and O(n²) does not mean 'slow' — it means that when the input doubles, one doubles its work and the other quadruples it.

This is why constants are dropped. An algorithm doing 100n operations and one doing 2n are both O(n), because at large enough n the shape of the curve is what determines whether the program finishes.

How to count

Find the operations whose count depends on the input size, and ask how many times each runs. A loop over the input is n. A loop inside a loop is n². A loop that halves its range each step is log n.

Then keep only the fastest-growing term. 3n² + 500n + 9000 is O(n²), because past a certain n the n² term dominates everything else — and it does so no matter how large those constants are.

def f(nums):            # n = len(nums)
    total = 0           # O(1)
    for x in nums:      # runs n times
        total += x      #   O(1) inside

    for a in nums:      # runs n times
        for b in nums:  #   runs n times each
            pass        #     -> n * n

    i = 1
    while i < len(nums):  # doubles each step -> log n
        i *= 2

    return total

# n + n^2 + log n  ->  O(n^2)

Note: The n² term swallows the rest. You do not add complexities, you keep the dominant one.

The classes you will actually meet

Space, and the stack people forget

Space complexity counts the extra memory you allocate beyond the input. A set of seen values is O(n). Two integer variables are O(1).

The trap is recursion. Every recursive call holds a stack frame until it returns, so a recursion of depth d costs O(d) space even if it allocates nothing. A recursive tree traversal is O(h) space, where h is the height — O(log n) balanced, O(n) for a degenerate tree.

Amortised analysis, and why append is O(1)

A Python list append is usually O(1), but occasionally the list is full and everything must be copied to a larger buffer, which is O(n). Averaged over many appends the cost is still constant — that is what 'amortised' means.

It works because the list grows geometrically. Resizes happen at exponentially spaced sizes, so the total copying across n appends sums to O(n), which is O(1) each. If it grew by a fixed 100 slots instead, resizes would happen every 100 appends and the total would be O(n²).