Big O Notation

Worst-case growth rates and comparing algorithms.

Big O describes how runtime or memory grows as input size n grows. We care about the dominant term, not whether you save 2× with a faster CPU.

Common complexities

O(1) — hash lookup. O(log n) — binary search. O(n) — scan an array. O(n log n) — good sorts. O(n²) — nested loops over n.