Big-O — the shape of your algorithm

Big-O describes how the work grows as the input grows. It's the single most-asked interview concept because it separates "this works on my laptop" from "this works at 100 million users."

The classes you must know

Notation	Name	Feels like
O(1)	Constant	Dictionary lookup, array indexing
O(log n)	Logarithmic	Binary search
O(n)	Linear	Single loop over a list
O(n log n)	Log-linear	Merge sort, Python's sorted()
O(n²)	Quadratic	Nested loop over the same list
O(2ⁿ)	Exponential	Naïve recursive Fibonacci
O(n!)	Factorial	Brute-force permutations

Rules of thumb

1. Drop constants. O(3n) is O(n). Constants matter in practice but not in classification.
2. Drop lower-order terms. O(n² + n) is O(n²).
3. Different inputs → different variables. O(n + m) when two collections have unrelated sizes.
4. Amortized vs worst case. Python list.append() is amortized O(1) — occasionally O(n) when it resizes.

Space complexity

Same idea for memory. A recursive function has O(depth) extra space on the call stack. A copy of a list is O(n) space.

The interview shortcut

Any nested loop over the same input → suspect O(n²). See if a hash map can turn it into O(n). This one substitution fixes 40% of "brute force → optimal" interview transitions.

Try it

1. Change the starter to time a list of 10 million ints. The list-scan gets ~10× slower; set lookup stays flat.
2. Write a function that finds duplicates in a list. First in O(n²) (nested loops), then in O(n) (using a set).