Basic, lesson 1 of 3
Complexity and what n allows
Before writing a line, read the input size. It tells you which complexity will pass, which tells you which algorithm to look for.
9 min, 3 checks
1Counting work
Big O counts how work grows with the input, ignoring constants. A loop over n items is O(n). A loop inside a loop over pairs is O(n^2): for n = 100 the pairs with i < j number 100 x 99 / 2 = 4,950. Halving a search range each step is O(log n).
| n | Fits in about a second | Typical tools |
|---|---|---|
| Up to 20 | O(2^n), O(n!) for tiny n | Brute force, bitmasks |
| Up to 5,000 | O(n^2) | Pairs, simple dynamic programming |
| Up to 1,000,000 | O(n log n) | Sorting, heaps, binary search |
| Up to 100,000,000 | O(n) | One pass, hashing, prefix sums |
Check 1
A double loop compares every pair (i, j) with i < j in a list of 100 items. How many comparisons?
Check 2
Binary search on a sorted list of 1,000,000 items. At most how many halvings does it take to find an item?
2Space and hidden costs
Memory counts too: a hash map of n items is O(n) extra space, and an interviewer who asks for O(1) space wants you to reuse the input or keep a few variables. Watch for hidden loops: in Python, slicing a list, "x in list", and building a string with += inside a loop are each O(n) per call.
Check 3
n is 1,000,000 and you have one second in C++. Which complexity is safe?
3 checks in this lesson. Sign in to keep your progress.