Complexity and Big-O

How to say what code costs in time and memory before running it. Every later chapter trades one of these costs for another.

Big-O notation

Also called Big-O, Big O, asymptotic notation, time complexity

What: Big-O describes how the running time or memory of an algorithm grows as the input size n grows, keeping only the fastest-growing term and dropping constants. 3n^2 + 5n is O(n^2).
Why: It lets you compare approaches before writing them and predict whether code will finish on large inputs. Every trade-off in this sheet is phrased in it.

Watch out

Forgetting that Big-O hides constants: on small inputs a simple O(n^2) loop can beat a clever O(n log n) solution, so measure when it matters.

Common growth rates

Also called O(1), O(log n), O(n log n), O(n^2), constant time, logarithmic time, linear time, quadratic time

What: From fastest to slowest: O(1) constant, O(log n) repeated halving, O(n) one pass, O(n log n) sorting, O(n^2) all pairs, O(2^n) all subsets, O(n!) all orderings.
Why: The rate tells you what kind of code produced it and what to aim for. At n = 1,000,000, O(n log n) is about 20 million steps while O(n^2) is a trillion.

Counting operations in loops

What: Multiply the costs of nested loops and add the costs of loops in sequence. A loop that halves or doubles its counter runs O(log n) times, and loops over two different inputs keep separate variables, as in O(n * m).
Why: Most complexity questions are answered by counting loops and the cost of the calls inside them, including the hidden ones.
Example: An outer loop over i and an inner loop from i + 1 to n runs n(n - 1)/2 times: still O(n^2). A loop doing i *= 2 up to n runs about log2(n) times.

Watch out

Ignoring library calls inside a loop: removing from the front of an array, indexOf, slicing and string copies are each O(n), which makes the loop O(n^2).

Best, worst and average case

Also called worst case, best case, average case

What: Worst case is the most work on any input of size n, best case the least, and average case the expected work over typical or random inputs. Quicksort is O(n log n) on average but O(n^2) in the worst case.
Why: Worst case is the safe promise to quote by default. Average case explains why hash maps and quicksort are fast in practice despite bad worst cases.

Space complexity and the call stack

Also called auxiliary space, memory complexity, call stack

What: The extra memory an algorithm uses beyond its input, as a function of n. Recursion counts too: every active call holds a stack frame, so recursion depth n costs O(n) space.
Why: Memory limits are real, and deep recursion can crash with a stack overflow long before the time limit is reached.

Watch out

Calling a recursive tree traversal O(1) space: it uses O(h) stack for height h, which is O(n) for a skewed tree.

Amortised cost

Also called amortized analysis, amortised

What: The average cost per operation over any long sequence of operations, even if a few single operations are expensive. Appending to a dynamic array is O(1) amortised because the rare O(n) resize doubles the capacity.
Why: It explains why dynamic arrays, resizing hash maps, monotonic stacks and union-find are fast overall even though one call can be slow.

Watch out

Confusing amortised with average case: an amortised bound holds for every sequence of operations and assumes nothing about the input.

Reading constraints

Also called constraints

What: The input limits in a problem hint at the expected complexity. Assume roughly 10^8 simple operations per second in C++, a little fewer in Java and JavaScript, and about ten times fewer in Python.
Why: Reading the limits first stops you over-engineering a small input or submitting something that cannot finish on a large one.
Example: n up to 20: O(2^n) is fine. Up to 500: O(n^3). Up to 5,000: O(n^2). Up to 10^5 or 10^6: O(n log n) or O(n). Up to 10^9 or more: O(log n), O(sqrt n) or a formula.

Go deeper