Big-O and Complexity Analysis

Big-O describes the upper bound on how an algorithm’s work grows as the input size n grows large, ignoring constant factors and lower-order terms.

Core idea

• Big-O measures growth, not seconds: count operations as a function of n (input size), not wall-clock time.
• Drop constants: 5n is O(n).
• Drop lower-order terms: n^2 + n + 100 is O(n^2) (keep the fastest-growing term).
• Time complexity = how operations grow. Space complexity = how extra memory grows (input itself not counted).

Complexity classes (best to worst)

• O(1) constant — work independent of n (index a list).
• O(log n) logarithmic — halve the input each step (binary search on sorted data).
• O(n) linear — one look at every item (sum, find max).
• O(n log n) linearithmic — good sorting (sorted).
• O(n^2) quadratic — nested loops over the whole input.
• O(2^n) exponential — work doubles per added item (naive recursive Fibonacci); a warning sign.

Growth at a glance

Reading loops

• Single loop over input: O(n).
• Nested loops, each over input: multiply -> O(n^2) (three deep -> O(n^3)).
• Two sequential loops: add -> O(n) + O(n) = O(n).
• Halving the range each pass: O(log n).
• No loop over n: O(1).
• Key rule: nested = multiply, sequential = add.

Watch out

• Big-O is worst case unless stated otherwise; on small n, constants can make O(n^2) beat O(n).
• Nested loops are not automatically O(n^2) — check what each bound actually depends on (a fixed-3 inner loop stays O(n)).
• Hidden loops count: x in a_list is O(n); inside a loop over n it becomes O(n^2).
• Amortized cost = long-run average per operation. list.append() is amortized O(1) (rare O(n) resize spread across many cheap appends).
• Never keep constants/small terms: O(2n + 5) -> O(n).