Complexity Analysis: Big-O, Amortized Analysis & Recurrences
Every lesson after this one ends with a sentence of the form "this runs in time and space". This lesson is where you learn to produce such a sentence yourself, prove it, and know what it does and does not promise about the program on your machine.
Why this exists
Suppose you time a sort on 10,000 numbers and it takes 12 milliseconds. What does that tell you about 10 million numbers? Nothing, unless you know how the running time grows. If the algorithm is linear it will take about 12 seconds; if it is quadratic it will take about 140 days. The number 12 ms is a fact about one input size, one machine, one compiler, one afternoon. The growth rate is a fact about the algorithm.
Complexity analysis is the discipline of describing an algorithm's cost as a function of its input size, stripped of everything that depends on the machine. The notation was invented for number theory: Paul Bachmann introduced the symbol in 1894 and Edmund Landau popularised it in 1909, both to describe error terms in asymptotic estimates. Donald Knuth imported it into computer science in the 1960s and, in a 1976 note titled "Big Omicron and Big Omega and Big Theta", fixed the conventions this lesson teaches. The analysis of algorithms as a field is Knuth's creation; The Art of Computer Programming is the reason we count operations rather than seconds.
Where it shows up: in every interview ("what is the complexity of that?"), every code review of a hot loop, every database query planner (which estimates cost before choosing a plan; see Query Planning & Optimization), every contest problem (whose time limit is a complexity bound in disguise), and every production incident where a system that was fine at 10,000 users falls over at 100,000. Several of the latter are in the real-world section below.
This lesson has three parts of increasing depth. The first is the notation and how to analyse loops and space: what you need for Modules 1 and 2. The second is amortized analysis, which explains why appending to a dynamic array is "O(1)" even though some appends copy the whole array; you need it for dynamic arrays, hash tables and union-find. The third is recurrence relations and the Master theorem, which you need for every divide-and-conquer algorithm from merge sort onwards.
Pattern triggers
Complexity analysis is a tool you reach for on cue. The cues:
| If the problem or situation says… | Think of… |
|---|---|
| "" or "" in the constraints | An or solution is expected; will time out. |
| "" or "" | is fine, is not. |
| "" | is fine. |
| "" or "" | Exponential (, ) is intended: bitmask DP or brute force over subsets. |
| "" or "" | Factorial () brute force over permutations is intended. |
| "" | The answer is or : binary search on the answer, fast exponentiation, math. |
| "Time Limit Exceeded" on a correct solution | Your complexity is one class too slow, or your constant is huge (slow I/O, allocation in a loop). |
| A loop whose body calls a library function on the whole collection | Hidden factor of : list.index, arr.includes, str.contains, remove(i) on an array list. |
A loop that does s += piece on a string | Potentially quadratic (see pitfalls). |
| "Each operation takes O(1) amortized" | Some operations are expensive, but any sequence of is ; think dynamic arrays, hash table resizing, union-find. |
| A function that calls itself on half (or two halves) of the input | A recurrence; reach for the Master theorem. |
| A function that calls itself on | A linear recurrence: unroll it, the answer is a sum. |
| The interviewer asks "can you do better?" | Compare your bound against the lower bound for the problem: to read the input, for comparison sorting, for searching a sorted array by comparisons. |
Intuition & first principles
Growth, not seconds
Measure a program's running time and you measure four things at once: the algorithm, the implementation, the machine and the input. Only the first is what you want to compare. The way out is to count abstract operations as a function of input size , and then to compare the shape of those functions for large . A function that grows like will eventually overtake any function that grows like , no matter how large the constant in front of the : is beaten by at and crushed by it at . "Eventually" is the key word; complexity analysis is a statement about large inputs, and it is silent about small ones.
The RAM model and what counts as a step
To count operations we need a machine. The standard one is the random-access machine (RAM): a single processor, an unbounded array of memory cells each holding a -bit word, and the following operations, each of which costs one step:
- arithmetic on words:
+ - * / %and comparisons; - bitwise operations and shifts;
- loading or storing one word at any address (hence "random access": address costs the same as address );
- a conditional or unconditional jump;
- a function call and return (constant work to set up a frame).
Two conventions matter. First, the word size is assumed large enough to hold any value in the problem, typically so that an index fits in a word; this is why we treat integer addition as even though adding two 1000-digit numbers is not. When numbers are genuinely huge (big integers, cryptography) you switch to bit complexity and count bit operations instead. Second, we charge one step for a memory access, which real machines violate by a factor of 100 or more between a cache hit and a cache miss. The model is a deliberate simplification; the section on constants and cache effects tells you when it lies.
Formally the model was pinned down by Cook and Reckhow in 1973; CLRS Chapter 2 gives the version everyone uses.
Counting steps for a concrete loop
# fragment — counting steps, not meant to be run
def sum_array(a): # n = len(a)
total = 0 # 1 step
for x in a: # loop runs n times; test + advance: ~2 steps each
total += x # 1 step, n times
return total # 1 step
Total: steps. Change the compiler and the "3" becomes 2 or 5; change the machine and each step takes 0.3 ns or 3 ns. What survives every such change is that the count is a linear function of . We write and, from then on, say "linear time".
Mechanics I: the notation, precisely
Big-O, Θ and Ω: formal definitions
Let and be functions from positive integers to non-negative reals.
(" is big-O of ") means there exist constants and such that
is an asymptotic upper bound on . The constants and are called witnesses; to prove an claim you exhibit them.
means there exist and such that for all . An asymptotic lower bound.
means both: there exist and with for . A tight bound; and grow at the same rate.
Two more, less common: (little-o) means grows strictly slower than : for every there is an with for ; equivalently . is the mirror image: grows strictly faster. So , , but because the ratio tends to 3, not 0.
The "" in is an abuse of notation; it means , membership in a set of functions. It is not symmetric: is true, is false. Never write .
Proving a bound with witnesses
Claim. .
Proof. We need and with for all . Divide by : we need . Since for , the choice , works: .
Tighter witnesses exist. With we need , i.e. : so , also works (check : ; and fails: ). There is no "right" pair; any pair that works is a proof.
Claim. .
Proof. Upper bound as above. Lower bound: for all , so , .
Claim. .
Proof. Suppose for all . Then for all , which fails at . Contradiction.
Claim. for any constants .
Proof. , and is a positive constant. So works. This is why we write without a base.
Rules you may use without re-proving them
- Drop constants: .
- Drop lower-order terms: if then . So .
- Sum rule (sequential code): . Two loops one after another: the bigger one wins.
- Product rule (nested code): . A loop of iterations whose body costs .
- Transitivity: and imply .
- Polynomial beats polylog: for every and every . So .
- Exponential beats polynomial: for every and every .
- Logarithm of a factorial: (Stirling). This is the comparison-sorting lower bound.
Best, average and worst case
Big-O bounds a function, and an algorithm has several functions you could bound: its running time on the worst input of size , on the best input, or averaged over inputs drawn from some distribution. These are different quantities, and three algorithms show how different:
Quicksort. With the first element as pivot, an already-sorted array makes every partition split into and , giving comparisons. On a random permutation the expected number of comparisons is about , which is . Best case (perfectly balanced splits) is also . So quicksort is worst case and average case, and saying "quicksort is " without qualification is wrong.
Hash table lookup. With a good hash function and load factor kept constant, a lookup is expected: the expected chain length is the load factor. If every key lands in the same bucket, a lookup is . That worst case is reachable on purpose (hash-flooding attacks, see real-world uses), which is why Java 8 converts a bucket with 8 or more entries into a red-black tree, making the worst case for Comparable keys.
Insertion sort on nearly-sorted input. Insertion sort does element moves where is the number of inversions (pairs out of order). On a random permutation is about (our check on gave 250,569 shifts against the expected 249,750), so . On an array with 10 adjacent swaps, and the sort ran in 10 shifts: . This is why Timsort and introsort switch to insertion sort for small or nearly-sorted runs.
The convention: when a bound is stated without qualification it is the worst case. Say "expected" or "average" when you mean that, and say what distribution you are averaging over.
The common classes
| Name | Typical source | |||||
|---|---|---|---|---|---|---|
| constant | 1 | 1 | 1 | 1 | array index, hash lookup (expected), arithmetic | |
| logarithmic | 3.3 | 10 | 20 | 30 | binary search, balanced-tree operation, halving loop | |
| square root | 3.2 | 32 | 1,000 | 31,623 | trial division, sqrt decomposition | |
| linear | 10 | 1,000 | one pass, two pointers, BFS on a path | |||
| linearithmic | 33 | merge sort, heap sort, sort-then-scan | ||||
| quadratic | 100 | all pairs, insertion sort, naive string concat | ||||
| cubic | 1,000 | Floyd-Warshall, naive matrix multiply, all triples | ||||
| exponential | 1,024 | — | — | all subsets, naive Fibonacci | ||
| factorial | — | — | all permutations, brute-force TSP |
Values are rounded; a dash means the number is too large to be meaningful (more than the atoms in the observable universe, about ).
flowchart LR
A["O(1)"] --> B["O(log n)"] --> C["O(sqrt n)"] --> D["O(n)"] --> E["O(n log n)"] --> F["O(n^2)"] --> G["O(n^3)"] --> H["O(2^n)"] --> I["O(n!)"]
style A fill:#2e7d32,color:#fff
style B fill:#2e7d32,color:#fff
style C fill:#558b2f,color:#fff
style D fill:#558b2f,color:#fff
style E fill:#f9a825,color:#000
style F fill:#ef6c00,color:#fff
style G fill:#d84315,color:#fff
style H fill:#b71c1c,color:#fff
style I fill:#b71c1c,color:#fff
What can you handle in about one second?
A compiled language on a modern desktop core executes roughly simple operations per second inside a tight loop; take that as a rule of thumb (Python is closer to ; a very simple loop in C++ can hit ). The largest with , computed exactly:
| Complexity | Largest in ~1 s at ops/s | Where you see that limit |
|---|---|---|
| Reading input is the bottleneck. | ||
| Sorting a few million items. | ||
| Sqrt decomposition, Mo's algorithm at . | ||
| Contest constraints of mean "quadratic is fine". | ||
| 464 | means "cubic is fine": Floyd-Warshall. | |
| 26 | Subset enumeration. | |
| 22 | Bitmask DP over subsets. | |
| 11 | Permutation brute force. |
These are the numbers behind the pattern-triggers table. In a contest with a 1-second limit and , the table says is intended and is 400 seconds. Memorise the rows for , , , and .
Mechanics II: analysing code
Simple and nested loops
A loop that runs times with an body is . Two nested loops each running times are . Three are . The sum rule says sequential loops add and the larger dominates: a loop of followed by a nested is .
The common trap is a loop whose body looks but is not. if x in some_list is . arr.remove(0) on an array list shifts everything: . s = s + ch on an immutable string copies: . Each turns an loop into . The lesson Your Language's Data Structures is the table of these costs for each language.
Dependent bounds: the triangle
# fragment — pairs i < j
for i in range(n):
for j in range(i + 1, n):
visit(i, j)
The inner loop runs times for each , so the total is
For that is 45 iterations, half of the an independent double loop would do. The constant halves; the class does not change. The sum is worth knowing cold, along with and .
Halving loops
# fragment — halving
while n > 0:
n //= 2
Each iteration divides by 2, so after iterations has become , which reaches 0 when , i.e. . For that is exactly 20 iterations. Any loop whose variable is multiplied or divided by a constant each step is . A nested pair, an outer loop with an inner halving loop, is .
Two-pointer loops
# fragment — two pointers
lo, hi = 0, n - 1
while lo < hi:
if condition(lo, hi):
lo += 1
else:
hi -= 1
Each iteration moves exactly one pointer one step toward the other, and they start apart, so there are at most iterations: . The argument generalises: find a quantity (here hi - lo) that strictly decreases every iteration and is bounded below, and the iteration count is bounded by its initial value. This is a progress measure, and it is the same idea as a termination proof in Recursion & Mathematical Induction.
The "amortized loop": an inner while that looks quadratic
# fragment — sliding window
left = 0
for right in range(n):
add(a[right])
while window_invalid():
remove(a[left])
left += 1
Nested loops, so is it ? No. Count the work by what it does to left, not by nesting: every iteration of the inner while increments left by one, left starts at 0 and never decreases, and left <= right < n, so the inner loop runs at most times in total across all iterations of the outer loop. Total work is . The same argument makes the monotonic-stack pattern linear: each element is pushed once and popped at most once, so there are at most stack operations regardless of how many pops any single iteration performs. This is amortized analysis in its simplest form, and we return to it below.
Space complexity
Space complexity counts memory cells used as a function of , with the same notation. Two conventions you must keep separate:
- Total space includes the input. An algorithm that reads an array of numbers uses total space no matter what.
- Auxiliary space is everything except the input: the extra memory the algorithm allocates. This is what "O(1) space" means in a problem statement: constant extra memory, with the input array given and possibly modified in place.
When an interviewer says "can you do it in O(1) space?" they mean auxiliary. When a problem says "in place", it means auxiliary (some texts allow for the recursion stack of quicksort and still call it in place).
The recursion stack counts. A recursive function with depth uses auxiliary space for its frames, even if it allocates nothing explicitly. Recursive DFS on a path graph of vertices uses stack. Merge sort uses for the merge buffer plus for the stack, so total auxiliary. Binary search recursively is auxiliary; iteratively it is . The recursion lesson covers the mechanics of frames and the per-language depth limits.
Amortized analysis, three ways
The problem
A dynamic array (Python list, Java ArrayList, C++ std::vector, JavaScript Array) stores elements in a contiguous block of some capacity. Appending into free capacity costs 1 step. When the array is full, append allocates a block of double the capacity, copies all existing elements, and then writes the new one: steps. So a single append is worst case. Yet everyone calls append "O(1)", and they are right in a precise sense: any sequence of appends starting from empty costs steps in total, so the average cost per operation over the sequence is . That average, guaranteed over every possible sequence of operations (not over a probability distribution), is the amortized cost.
Amortized analysis is not probabilistic. It says nothing about any single operation; it says that the expensive operations are rare enough, in a way you can prove, that the cheap ones pay for them. Tarjan's 1985 paper "Amortized Computational Complexity" named the technique and gave the three methods below.
Method 1: aggregate analysis
Sum the total cost of the operations directly and divide by .
Start with capacity 1. Resizes happen when the size reaches , i.e. before appends number The -th resize copies elements. For appends there are resizes at most, and the copies total
Add the writes themselves: total cost . Amortized cost per append: , which is .
Aggregate analysis is the most direct method and the one to try first. Its weakness is that it gives every operation the same amortized cost, which is awkward when operations differ (push vs pop, insert vs delete).
Method 2: the accounting method (credits)
Charge each operation an amortized cost that may differ from its actual cost. When amortized exceeds actual, the surplus is stored as credit on specific objects in the data structure; when actual exceeds amortized, stored credit pays the difference. The method is valid as long as the total credit in the structure is never negative, because then the sum of amortized costs is at least the sum of actual costs.
Claim. Charging 3 credits per append suffices for a doubling dynamic array.
Proof. Each append pays 3: 1 for writing itself, 1 saved on itself to pay for copying itself at the next resize, and 1 saved to pay for copying one element that was already present at the last resize and has no credit of its own. Consider the moment just after a resize to capacity : the array holds elements, none of which has credit (it was spent on the copy), and has free slots. Before the next resize, appends occur, each depositing 1 credit on itself and 1 credit on one of the old elements. When the array fills at elements, every element has exactly 1 credit, and the resize copies elements using those credits. Credit never goes negative.
Running the bank for 9 appends (verified by script): after each append the balance is 2, 3, 3, 5, 3, 5, 7, 9, 3. It dips to 3 right after each resize and never below.
Can 2 credits work? No: the first element after a resize would need to pay for itself, its own future copy and an old element's copy, which is 3 units. (With 2 credits the balance after append 5 would be .) The constant 3 is tight for this charging scheme with doubling; a growth factor of 1.5, as used by some std::vector implementations and Java's ArrayList, needs more credits per append but wastes less memory.
Method 3: the potential method
Define a potential function mapping each state of the data structure to a non-negative number, with . The amortized cost of an operation is
its actual cost plus the change in potential. Summing over operations, the potentials telescope:
so total amortized cost bounds total actual cost. Potential is credit viewed globally: is the bank balance, and you no longer have to say which object holds which coin.
For the doubling array, take . Right after a resize, size $= $ capacity so ; as the array fills, climbs to size capacity, . It is never negative once size capacity, which holds after the first append.
- Append without resize: actual cost 1, size increases by 1, capacity unchanged: . Amortized .
- Append with resize from size $= $ capacity : actual cost . Before: . After: size , capacity , . . Amortized .
Every append has amortized cost exactly 3 under this potential.
Trace table: the potential method on 9 appends
Capacity starts at 1, size at 0, . All values computed by script. (The first row has by definition even though ; the potential method only needs and for all later states, and we define .)
| Append # | size before | capacity before | elements copied | actual cost | before | after | amortized | capacity after |
|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 2 | 1 |
| 2 | 1 | 1 | 1 | 2 | 1 | 2 | 3 | 2 |
| 3 | 2 | 2 | 2 | 3 | 2 | 2 | 3 | 4 |
| 4 | 3 | 4 | 0 | 1 | 2 | 4 | 3 | 4 |
| 5 | 4 | 4 | 4 | 5 | 4 | 2 | 3 | 8 |
| 6 | 5 | 8 | 0 | 1 | 2 | 4 | 3 | 8 |
| 7 | 6 | 8 | 0 | 1 | 4 | 6 | 3 | 8 |
| 8 | 7 | 8 | 0 | 1 | 6 | 8 | 3 | 8 |
| 9 | 8 | 8 | 8 | 9 | 8 | 2 | 3 | 16 |
Totals: actual , amortized . The amortized total exceeds the actual total by exactly , as the telescoping sum predicts. Four of the nine appends copied the entire array, and the amortized cost of each was still 3.
Second example: the binary counter
A -bit counter is incremented times from 0. An increment flips the trailing 1s to 0 and one 0 to 1; its cost is the number of bits flipped. Worst case per increment: (from to ). Amortized:
- Aggregate. Bit 0 flips every increment: times. Bit 1 flips every second increment: . Bit flips times. Total . Amortized per increment. (Script: 8 increments cost 15 flips, 16 cost 31, 1000 cost 1994.)
- Accounting. Charge 2 per increment. Each increment sets exactly one bit to 1; pay 1 for that flip and leave 1 credit on the bit. Every 1 bit therefore carries a credit, and when an increment clears trailing 1s, those credits pay for the flips. Credit never goes negative.
- Potential. $\Phi = $ number of 1 bits. An increment that clears ones and sets one costs and changes by . Amortized .
Third example: a queue from two stacks
Implement a FIFO queue with two LIFO stacks, inbox and outbox. enqueue(x) pushes onto inbox. dequeue() pops from outbox; if outbox is empty, first pop everything from inbox and push it onto outbox (reversing the order), then pop. A single dequeue can cost stack operations when inbox holds items. Yet:
Potential. . enqueue: actual 1, , amortized 3. dequeue with transfer of items: actual , , amortized 1. dequeue without transfer: actual 1, , amortized 1. So any sequence of enqueues and dequeues costs at most stack operations. Each element is pushed at most twice and popped at most twice in its lifetime, which the aggregate view makes obvious: at most operations in total.
This structure is Queues, Deques & Circular Buffers territory and a standard interview problem; the amortized argument is what the interviewer wants to hear.
Amortized is not worst-case
An amortized append can still take 100 ms when it copies a 100-million-element array. If a single operation's latency matters (a real-time system, a UI frame, a network request with a deadline), amortized bounds are not enough and you need a structure with worst-case guarantees, such as a deque implemented as a ring buffer with incremental resizing or a balanced tree. Redis Internals shows this trade-off in production: its hash tables rehash incrementally, a few buckets per operation, precisely to avoid the one giant resize.
Recurrences
What a recurrence is
A recursive algorithm's running time is naturally a recurrence: an equation that defines in terms of on smaller arguments plus the non-recursive work. Merge sort splits in two, sorts each half, and merges in linear time:
Solving the recurrence means finding a closed form, here. Three methods, from most general to most mechanical.
Method 1: substitution (guess and prove by induction)
Guess the form, then prove it by induction. For merge sort, guess for some and all (we handle separately since ). Inductive step: assume it for ,
whenever . The base cases need large enough to cover ; pick . So . The matching lower bound is the same argument with .
Substitution works for anything, but you must already know the answer. Its classic trap is proving a bound that is too tight to close the induction: trying to show for gives , which is not , so the induction fails, correctly, because the claim is false.
Method 2: recursion trees
Draw the recursion as a tree. Each node is a subproblem labelled with its non-recursive cost; the children are the recursive calls. Sum the costs level by level, then sum the levels.
For :
flowchart TD
R["n"] --> A["n/2"]
R --> B["n/2"]
A --> C["n/4"]
A --> D["n/4"]
B --> E["n/4"]
B --> F["n/4"]
C --> C1["…"]
D --> D1["…"]
E --> E1["…"]
F --> F1["…"]
| Level | Subproblems | Size each | Cost each | Cost of level |
|---|---|---|---|---|
| 0 | 1 | |||
| 1 | 2 | |||
| 2 | 4 | |||
| (leaves) | 1 |
Every level costs and there are levels, so . For the exact sum with is (verified).
The recursion tree exposes three regimes that the Master theorem is about to formalise. If the per-level cost shrinks geometrically going down, the root dominates and . If it stays constant, every level contributes equally and . If it grows geometrically, the leaves dominate and .
Method 3: the Master theorem
For recurrences of the form
with asymptotically positive, let so that is the number of leaves of the recursion tree (there are leaves). Compare with :
| Case | Condition | Result | Intuition |
|---|---|---|---|
| 1 | for some | is polynomially smaller; leaves dominate. | |
| 2 | Every level costs the same. | ||
| 3 | for some , and for some and large | is polynomially larger; the root dominates. The second condition ("regularity") holds for every polynomial you will meet. |
flowchart TD
S["T of n = a T of n over b, plus f of n<br/>compute k = log_b a"] --> Q{"compare f with n^k"}
Q -->|"f is polynomially smaller"| C1["Case 1<br/>Theta(n^k)"]
Q -->|"f = Theta(n^k)"| C2["Case 2<br/>Theta(n^k log n)"]
Q -->|"f is polynomially larger<br/>and regular"| C3["Case 3<br/>Theta of f"]
Q -->|"neither, e.g. f = n^k log n"| G["Gap: use extended case 2,<br/>Akra-Bazzi or a recursion tree"]
Worked examples, every one of which you will meet later in the course:
| Algorithm | Recurrence | Case | Result | |
|---|---|---|---|---|
| Binary search | ; | 2 | ||
| Merge sort | ; | 2 | ||
| Tree traversal | ; | 1 | ||
| Karatsuba multiplication | ; | 1 | ||
| Strassen matrix multiply | ; | 1 | ||
| Naive 8-way matrix multiply | ; | 1 | ||
| Quickselect (balanced) | ; , regular | 3 | ||
| "Sort then recurse on one half" | ; , regular | 3 |
The Strassen row is the reason that algorithm matters: cutting one multiplication out of eight changes the exponent from 3 to 2.807, and the Master theorem makes that visible in one line.
When the Master theorem does not apply
Subtractive recurrences. (quicksort's worst case, or the triangle loop written recursively) is not of the form . Unroll it: . For that is 5050 (verified). More generally gives , and (Tower of Hanoi) gives .
The gap between cases. has and , which is larger than but not polynomially larger: there is no with , since . So the classic three cases are silent. Three ways out:
- Recursion tree. Level has subproblems of size , each costing , so the level costs . Summing over to : . (For the exact level sum is , verified.)
- Extended case 2. CLRS (4th edition, Theorem 4.1) extends case 2 to for , giving . Here , so .
- Akra–Bazzi. For with , , and small perturbations , find the unique with ; then
For : gives , and , so . Akra–Bazzi also handles unequal splits such as (the solution gives ) and floors and ceilings, which it absorbs into . You rarely need it in an interview, but it is the general tool when the Master theorem's shape does not fit.
Non-constant number of subproblems or non-polynomial . or need a change of variables () and then one of the methods above.
The ladder: how analysis drives the climb
Complexity analysis is not an after-the-fact label; it is what tells you a solution can be improved and roughly how. The standard ladder on a standard problem, counting pairs in an array that sum to a target:
| Rung | Idea | Time | Space | Why it improves on the rung below |
|---|---|---|---|---|
| Brute force | Check every pair with . | — (baseline) | ||
| Better | Sort, then for each element binary-search its complement. | or | Replaces the inner linear scan () with a logarithmic search (). | |
| Better | Sort, then two pointers from both ends. | Same class as binary search but one pass after the sort: a smaller constant and no per-element search. | ||
| Optimal (time) | Hash set of seen values; one pass. | expected | Replaces the sort with expected lookups, trading space for time. Cannot beat : every element must be read. |
Each step says the same thing: find the term that dominates, and ask which operation produces it. In the brute force it is the inner loop; in the sorted version it is the sort; in the hashed version nothing is left but reading the input. That is how you know you are done. Two Pointers and Hash Tables develop the two optimal rungs.
Correctness: what a complexity claim is a claim about
A complexity statement is a theorem with four parts, and a complete answer names all four: which resource (time or space, and total vs auxiliary), which case (worst, expected, amortized), in terms of which parameters ( alone, or and , or and ), and the bound with its tightness ( or ).
To prove the claim you need two things: an upper bound (a count of steps that is at most ) and, for , a lower bound via an input family that forces work. Most of the proofs on this page followed that template: the witness proofs for polynomials, the per-level sums of recursion trees, the potential functions whose telescoping gives an upper bound on actual cost. When you cannot produce the lower-bound family, say , not ; it is still correct and it is honest.
The lower bounds you may quote without proof: reading items is ; comparison sorting is because there are permutations and each comparison distinguishes at most a factor of 2, so comparisons are needed; searching a sorted array by comparisons is by the same counting argument over possible positions. Module 2's lesson on non-comparison sorts and the lower bound proves the sorting bound in full; until then, Sorting & Searching has the overview.
Complexity in practice: constants, cache and the machine
Two O(n) scans that differ by two orders of magnitude
Big-O treats a memory access as one step. Real memory is a hierarchy: an L1 cache hit costs about 1 ns, a main-memory access about 80–100 ns, and the hardware fetches memory in cache lines of 64 bytes and prefetches sequential access patterns. Scanning an array touches memory sequentially: each cache line serves 8 consecutive 8-byte values, and the prefetcher has the next line ready. Traversing a linked list follows a pointer to wherever the next node happens to be allocated; if nodes were allocated out of order, every step is a cache miss.
We measured both on one machine, 10 million 8-byte values: the array scan took about 5 ms; a linked list whose nodes happened to be contiguous and in order took about 25 ms (5× slower, the pointer dependency defeats vectorisation and prefetch); a linked list whose nodes were allocated in shuffled order took about 1.7 s, roughly 300× slower than the array. Three algorithms, a factor of 300 between the fastest and slowest. The numbers are specific to that machine (a laptop, MSVC, /O2) and will differ on yours; the ordering will not. Ratios of 10–100× between a sequential scan and a pointer chase over a cache-sized working set are typical in the literature and in Performance Benchmarks.
How Data Structures Live in Memory is the full treatment: cache lines, pointer chasing, allocation patterns, and why a sorted std::vector with binary search often beats std::map despite the same . The point for this lesson is narrower: Big-O ranks algorithms; it does not rank implementations of the same algorithm, and it does not predict constants. When two solutions are in the same class, or within a of each other, measure.
When the constant is the whole story
- with is : in C++ about 20 ms, in Python about 2 s. Same algorithm, same class, 100× apart.
- Hash maps are expected but with a constant of a hash computation plus one or two cache misses; a linear scan of an array of 16 elements is usually faster than a hash lookup, which is why small-map optimisations exist.
- Radix sort is versus for comparison sort; for 32-bit keys passes, and radix sort wins for large but loses for small because of its setup cost and worse cache behaviour.
The order of operations
First get the right complexity class. Then, if it matters, measure and optimise the constant. Optimising constants in a quadratic algorithm is wasted effort once doubles twice; choosing the right class and never measuring is how an linked-list solution ends up 50× slower than the array one it replaced.
Implementation: a harness that measures growth
The best way to internalise growth rates is to watch them. The harness below times an , an and an function at four sizes, prints the ratio of consecutive times, and asserts that the quadratic function's growth is the fastest. The theoretical ratios when doubles are 2, about 2.2 (for these ), and 4; when grows 8× they are 8, about 11, and 64. Sizes are small so the whole thing runs in well under five seconds in each language; the compiled versions use larger so that the measurements rise above timer resolution.
import time
def linear(n: int) -> int:
"""O(n): one pass over 0..n-1."""
total = 0
for i in range(n):
total += i & 7
return total
def n_log_n(n: int) -> int:
"""O(n log n): for each i, a halving loop of ~log2(n) steps."""
total = 0
for i in range(n):
m = n
while m > 0:
total += m & 1
m >>= 1
return total
def quadratic(n: int) -> int:
"""O(n^2): every ordered pair (i, j)."""
total = 0
for i in range(n):
for j in range(n):
total += (i ^ j) & 1
return total
def best_of(fn, n: int, reps: int = 5) -> float:
"""Smallest wall-clock time over `reps` runs, in seconds."""
best = float("inf")
for _ in range(reps):
t0 = time.perf_counter()
fn(n)
best = min(best, time.perf_counter() - t0)
return best
def main() -> None:
sizes = [250, 500, 1000, 2000]
fns = [("O(n)", linear), ("O(n log n)", n_log_n), ("O(n^2)", quadratic)]
for _, fn in fns: # warm-up
fn(sizes[0])
ratios = {}
print(f"{'class':<12}{'n':>8}{'seconds':>12}{'t(n)/t(n/2)':>14}")
for name, fn in fns:
prev = None
for n in sizes:
t = best_of(fn, n)
ratio = (t / prev) if prev else float("nan")
print(f"{name:<12}{n:>8}{t:>12.6f}{ratio:>14.2f}")
prev = t
t_small, t_big = best_of(fn, sizes[0]), best_of(fn, sizes[-1])
ratios[name] = t_big / t_small # n grew 8x
print("growth from n=250 to n=2000:", {k: round(v, 1) for k, v in ratios.items()})
# 8x more input: linear should grow ~8x, quadratic ~64x.
assert ratios["O(n^2)"] > ratios["O(n)"], "quadratic must grow faster than linear"
assert ratios["O(n^2)"] > ratios["O(n log n)"], "quadratic must grow faster than n log n"
assert ratios["O(n^2)"] > 16, f"quadratic grew only {ratios['O(n^2)']:.1f}x for 8x input"
print("OK")
if __name__ == "__main__":
main()
import java.util.function.IntToLongFunction;
public class ComplexityHarness {
// O(n): one pass over 0..n-1.
static long linear(int n) {
long total = 0;
for (int i = 0; i < n; i++) total += i & 7;
return total;
}
// O(n log n): for each i, a halving loop of ~log2(n) steps.
static long nLogN(int n) {
long total = 0;
for (int i = 0; i < n; i++) {
int m = n;
while (m > 0) { total += m & 1; m >>= 1; }
}
return total;
}
// O(n^2): every ordered pair (i, j).
static long quadratic(int n) {
long total = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) total += (i ^ j) & 1;
return total;
}
static long sink = 0; // keeps the JIT from deleting the work
static double bestOf(IntToLongFunction fn, int n, int reps) {
double best = Double.MAX_VALUE;
for (int r = 0; r < reps; r++) {
long t0 = System.nanoTime();
sink += fn.applyAsLong(n);
best = Math.min(best, (System.nanoTime() - t0) / 1e9);
}
return best;
}
public static void main(String[] args) {
int[] sizes = {250, 500, 1000, 2000};
String[] names = {"O(n)", "O(n log n)", "O(n^2)"};
IntToLongFunction[] fns = {ComplexityHarness::linear, ComplexityHarness::nLogN, ComplexityHarness::quadratic};
for (IntToLongFunction fn : fns) // warm-up so the JIT compiles each function
for (int i = 0; i < 2000; i++) sink += fn.applyAsLong(sizes[0]);
double[] growth = new double[3];
System.out.printf("%-12s%8s%12s%14s%n", "class", "n", "seconds", "t(n)/t(n/2)");
for (int k = 0; k < fns.length; k++) {
double prev = -1;
for (int n : sizes) {
double t = bestOf(fns[k], n, 5);
System.out.printf("%-12s%8d%12.6f%14.2f%n", names[k], n, t, prev < 0 ? Double.NaN : t / prev);
prev = t;
}
growth[k] = bestOf(fns[k], sizes[3], 5) / bestOf(fns[k], sizes[0], 5);
}
System.out.printf("growth from n=250 to n=2000: linear %.1fx, n log n %.1fx, quadratic %.1fx%n",
growth[0], growth[1], growth[2]);
if (!(growth[2] > growth[0])) throw new AssertionError("quadratic must grow faster than linear");
if (!(growth[2] > growth[1])) throw new AssertionError("quadratic must grow faster than n log n");
if (!(growth[2] > 16)) throw new AssertionError("quadratic grew only " + growth[2] + "x for 8x input");
System.out.println("OK " + (sink != 0));
}
}
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <vector>
// O(n): one pass over 0..n-1.
std::uint64_t linear(int n) {
std::uint64_t total = 0;
for (int i = 0; i < n; i++) total += i & 7;
return total;
}
// O(n log n): for each i, a halving loop of ~log2(n) steps.
std::uint64_t n_log_n(int n) {
std::uint64_t total = 0;
for (int i = 0; i < n; i++) {
int m = n;
while (m > 0) { total += m & 1; m >>= 1; }
}
return total;
}
// O(n^2): every ordered pair (i, j).
std::uint64_t quadratic(int n) {
std::uint64_t total = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) total += (i ^ j) & 1;
return total;
}
volatile std::uint64_t sink = 0; // keeps the optimizer from deleting the work
double best_of(const std::function<std::uint64_t(int)>& fn, int n, int reps = 5) {
double best = 1e300;
for (int r = 0; r < reps; r++) {
auto t0 = std::chrono::steady_clock::now();
sink = sink + fn(n);
double t = std::chrono::duration<double>(std::chrono::steady_clock::now() - t0).count();
if (t < best) best = t;
}
return best;
}
int main() {
// Larger n than the Python version: compiled code is ~100x faster per step.
std::vector<int> sizes = {2000, 4000, 8000, 16000};
const char* names[] = {"O(n)", "O(n log n)", "O(n^2)"};
std::function<std::uint64_t(int)> fns[] = {linear, n_log_n, quadratic};
double growth[3];
std::printf("%-12s%8s%12s%14s\n", "class", "n", "seconds", "t(n)/t(n/2)");
for (int k = 0; k < 3; k++) {
double prev = -1;
for (int n : sizes) {
double t = best_of(fns[k], n);
std::printf("%-12s%8d%12.6f%14.2f\n", names[k], n, t, prev < 0 ? 0.0 : t / prev);
prev = t;
}
growth[k] = best_of(fns[k], sizes[3]) / best_of(fns[k], sizes[0]);
}
std::printf("growth from n=2000 to n=16000: linear %.1fx, n log n %.1fx, quadratic %.1fx\n",
growth[0], growth[1], growth[2]);
if (!(growth[2] > growth[0])) { std::puts("FAIL: quadratic must grow faster than linear"); return 1; }
if (!(growth[2] > growth[1])) { std::puts("FAIL: quadratic must grow faster than n log n"); return 1; }
if (!(growth[2] > 16)) { std::puts("FAIL: quadratic grew too slowly"); return 1; }
std::puts("OK");
return 0;
}
// O(n): one pass over 0..n-1.
function linear(n: number): number {
let total = 0;
for (let i = 0; i < n; i++) total += i & 7;
return total;
}
// O(n log n): for each i, a halving loop of ~log2(n) steps.
function nLogN(n: number): number {
let total = 0;
for (let i = 0; i < n; i++) {
let m = n;
while (m > 0) { total += m & 1; m >>= 1; }
}
return total;
}
// O(n^2): every ordered pair (i, j).
function quadratic(n: number): number {
let total = 0;
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++) total += (i ^ j) & 1;
return total;
}
let sink = 0; // keeps the JIT from deleting the work
function bestOf(fn: (n: number) => number, n: number, reps = 5): number {
let best = Infinity;
for (let r = 0; r < reps; r++) {
const t0 = performance.now();
sink += fn(n);
best = Math.min(best, (performance.now() - t0) / 1000);
}
return best;
}
function main(): void {
const sizes = [1000, 2000, 4000, 8000];
const fns: Array<[string, (n: number) => number]> = [["O(n)", linear], ["O(n log n)", nLogN], ["O(n^2)", quadratic]];
for (const [, fn] of fns) for (let i = 0; i < 2000; i++) sink += fn(sizes[0]); // warm-up for the JIT
const growth: Record<string, number> = {};
console.log("class".padEnd(12) + "n".padStart(8) + "seconds".padStart(12) + "t(n)/t(n/2)".padStart(14));
for (const [name, fn] of fns) {
let prev = -1;
for (const n of sizes) {
const t = bestOf(fn, n);
console.log(name.padEnd(12) + String(n).padStart(8) + t.toFixed(6).padStart(12) + (prev < 0 ? "-" : (t / prev).toFixed(2)).padStart(14));
prev = t;
}
growth[name] = bestOf(fn, sizes[3]) / bestOf(fn, sizes[0]);
}
console.log("growth from n=1000 to n=8000:", Object.fromEntries(Object.entries(growth).map(([k, v]) => [k, v.toFixed(1)])));
if (!(growth["O(n^2)"] > growth["O(n)"])) throw new Error("quadratic must grow faster than linear");
if (!(growth["O(n^2)"] > growth["O(n log n)"])) throw new Error("quadratic must grow faster than n log n");
if (!(growth["O(n^2)"] > 16)) throw new Error("quadratic grew only " + growth["O(n^2)"] + "x for 8x input");
console.log("OK", sink !== 0);
}
main();
A representative Python run on the authoring machine (your numbers will differ, the ratios should not):
class n seconds t(n)/t(n/2)
O(n) 250 0.000009 nan
O(n) 500 0.000020 2.14
O(n) 1000 0.000041 2.11
O(n) 2000 0.000082 1.99
O(n log n) 250 0.000169 nan
O(n log n) 500 0.000382 2.26
O(n log n) 1000 0.000857 2.24
O(n log n) 2000 0.001914 2.23
O(n^2) 250 0.002940 nan
O(n^2) 500 0.013992 4.76
O(n^2) 1000 0.057745 4.13
O(n^2) 2000 0.237110 4.11
growth from n=250 to n=2000: {'O(n)': 9.1, 'O(n log n)': 11.4, 'O(n^2)': 80.1}
The doubling ratios land near 2, 2.2 and 4 as predicted. The growth of 9.1× rather than 8× and the quadratic 80× rather than 64× are timer noise at these tiny durations (the smallest measurement is 9 microseconds); the Java, C++ and TypeScript runs gave 63×, 66× and 64× for the quadratic. Try it: swap in your own function and read its class off the ratios. A ratio near 2 per doubling is linear, near 4 is quadratic, near 8 is cubic, and a ratio that itself doubles each time is exponential.
Real-world uses
Complexity analysis is not an academic exercise; a wrong class is one of the most common root causes of production incidents and of expensive hardware.
- Query planners estimate complexity before running anything. A relational database chooses between a nested-loop join (), a hash join () and a sort-merge join () by estimating row counts and costing each plan; the estimates are exactly the analysis in this lesson applied to table statistics. When the statistics are stale, the planner picks the quadratic plan and a query that took 20 ms takes 20 minutes. See Query Planning & Optimization and Indexing Deep Dive ( B-tree lookups versus scans).
- Hash-flooding denial of service (2011). Alexander Klink and Julian Wälde showed at the 28th Chaos Communication Congress that an attacker who can choose request parameter names can make them all collide in the server's hash table, turning parameter parsing into : a few hundred kilobytes of POST data kept a CPU core busy for minutes on PHP, Java, Python, Ruby and ASP.NET. The fixes were randomised hash seeds (Python 3.3's
PYTHONHASHSEED, Ruby, Perl) and, in Java 8, treeifying long buckets to cap the worst case at . The worst-case-versus-expected distinction on this page is the whole story. Hash Tables & Hashing in Depth covers the mitigation. - Catastrophic regex backtracking (Cloudflare, 2 July 2019). A WAF rule containing
.*(?:.*=.*)made the regex engine backtrack in or worse on certain inputs; CPU on every edge server hit 100% and the network returned 502s globally for 27 minutes. Cloudflare's post-mortem walks through the backtracking step counts. Backtracking regex engines are exponential in the worst case; automaton-based engines (RE2, Rust'sregex) are guaranteed linear. Regex Mastery and Module 7's regex-engines lesson cover both. - GTA Online's six-minute load screen (2021). A reverse-engineer found that the game parsed a 10 MB JSON catalogue of about 63,000 items with a
sscanf-based loop that calledstrlenon the whole remaining buffer for every token ( over the file), then de-duplicated items by linear scan of an array ( again). Fixing both cut load time by about 70%. Rockstar shipped the fix. Two quadratic loops on an input that had grown 10× since launch. - Operating-system schedulers. Linux's scheduler keeps runnable tasks in a red-black tree keyed by virtual runtime so that picking the next task is ; its predecessor, the O(1) scheduler, got its name from the constant-time pick it was designed for. CPU Scheduling has the details.
- Sorting libraries. Python's
sorted, Java'sArrays.sortfor objects and V8'sArray.prototype.sortall use Timsort, chosen because it is worst case and on already-sorted or nearly-sorted input, the best/average/worst distinction turned into a design decision. C++'sstd::sortis introsort: quicksort that switches to heap sort when recursion gets too deep, bounding the worst case at . - Capacity planning. Cache Sizing Math and Consistent Hashing are complexity analysis applied to fleets: how key count scales with nodes, and why rebalancing must be keys, not .
Pitfalls & edge cases
Writing the base of a logarithm as if it mattered. , and are the same class; the base is a constant factor. Write . The exception is the exponent: and are different classes because the base is now inside a power.
Dropping the wrong term. is , correct. is , correct. But is not when is an independent parameter; it stays . You may only drop terms that are dominated for all values of all parameters.
Confusing with . Saying "binary search is " is true (it is also ) and useless. When you know the tight bound, state or say "and this is tight". Interviewers read "" as "roughly ", so do not describe your algorithm as to be safe; it reads as not knowing.
"Hash maps are O(1)" without the caveats. Expected assumes a hash function that spreads keys and a load factor kept bounded by resizing. The worst case is (all keys collide), the resize is for that one operation (amortized ), and hashing a string key costs , which is not constant if keys are long. "O(1) expected, with to hash a key of length " is the complete answer.
Treating and as the same. For two inputs of sizes and , a nested loop is , not . Graph algorithms are stated in and for the same reason: BFS is , and writing is only right for dense graphs. When a problem has two sizes, your bound has two variables until you can prove one dominates.
String concatenation in a loop. Strings are immutable in Python, Java and JavaScript, so s = s + piece in the language model copies characters, and appends cost . In Java this is exactly what happens (the compiler's StringBuilder rewrite applies within a single expression, not across loop iterations): use StringBuilder. In CPython the s += t case has an in-place optimisation when s has no other references, which usually hides the cost, but it is an implementation detail that PyPy does not share and that fails the moment s is also stored elsewhere; use "".join(parts). V8 represents concatenations as ropes, so += is usually cheap, but flattening happens on first indexing. The portable answer in all three is a list of parts joined once, or a builder. C++ std::string::operator+= is amortized because std::string is a dynamic array.
Forgetting the recursion stack. "O(1) space" recursive solutions are usually space. Recursive in-order traversal of a tree is space, which is for a degenerate tree. The recursion lesson lists the per-language depth limits; Python's default of 1000 frames makes recursive DFS on a 10,000-node path graph crash, and that is a complexity bug, not a style choice.
Assuming library calls are free. sorted() inside a loop is per iteration. list.insert(0, x) is . in on a list is , on a set expected. substring in Java copies since JDK 7u6. Array.prototype.shift is in most engines. Your Language's Data Structures is the lookup table; check it before claiming a bound.
Off-by-one in loop bounds does not change the class, but it changes the answer. and are both and differ by . In an interview the class is what matters; in a trace table or an exact count, get the bound right.
Confusing amortized with average. Average-case bounds are over a probability distribution of inputs and can be violated by an adversary who picks inputs. Amortized bounds hold for every sequence of operations, adversarial or not. Quicksort's is average case; dynamic array append's is amortized. They are different guarantees.
Variations
- Expected (randomised) complexity. Bounds over the algorithm's own random choices rather than the input distribution: randomised quicksort is expected for every input, because the pivot choice is random. This is strictly stronger than average-case over inputs. Module 5's randomised-algorithms lesson develops it.
- Output-sensitive complexity. When the output size varies, bound in terms of it: enumerating all pairs that sum to a target is with a hash map; convex hull is for hull points (Chan's algorithm). Stating because the output could be quadratic undersells an algorithm that is linear when the output is small.
- Parameterised complexity. Bound in terms of and a structural parameter : for vertex cover of size is tractable for small even though the problem is NP-hard. Module 9's complexity-theory lesson covers P, NP and this escape hatch.
- Bit complexity. When numbers do not fit in a word (cryptography, big integers), count bit operations: schoolbook multiplication of two -bit numbers is , Karatsuba . Module 8's big-number capstone works in this model.
- The external-memory (I/O) model. Count block transfers between disk and memory rather than CPU steps; a B-tree lookup is I/Os for block size . Module 9's cache-efficient algorithms lesson and Storage Engines use this model.
- Competitive analysis. For online algorithms that must decide without seeing the future (caching, scheduling), compare against the optimal offline algorithm: LRU is -competitive for a cache of size . Module 9's online-vs-offline lesson and Caching Strategies cover it.
- Smoothed analysis. Spielman and Teng's 2004 explanation of why the simplex algorithm is fast in practice despite exponential worst cases: average over small random perturbations of a worst-case input. Rarely needed in interviews; mentioned so that you recognise the term.
Practice ladder
Analysis exercises (no platform)
Derive each bound on paper; the answers are collapsed.
- What is the time complexity of the following, in terms of ?
# fragment — exercise 1
for i in range(n):
j = 1
while j < n:
j *= 2
Answer
: the inner loop runs times for each of values of .
- And this one?
# fragment — exercise 2
i = n
while i > 0:
for j in range(i):
pass
i //= 2
Answer
. The inner loop runs times in total. A halving outer loop with a body proportional to the current value is linear, not : the sum of a geometric series is dominated by its first term.
- A function calls itself three times on inputs of size and does work outside the calls. Complexity?
Answer
. , and with regularity (). Case 3: .
- Prove that .
Answer
since any positive power of eventually dominates (L'Hôpital, or note that for every ).
- A stack supports
push,pop, andmultipop(k)which pops up to items. Show that any sequence of operations starting from empty costs .
Answer
Potential $\Phi = $ stack size. push: actual 1, , amortized 2. pop: actual 1, , amortized 0. multipop(k) popping items: actual , , amortized 0. Total amortized , so total actual . Equivalently: each item is pushed once and popped at most once, so at most stack operations.
- Solve .
Answer
. Recursion tree: every level costs (the sizes at each level sum to ) and the longest path has levels, the shortest ; both are . Akra–Bazzi: gives and , so .
Platform problems where complexity is the crux
Each of these is a problem whose naive solution is correct but one class too slow, or where the point of the problem is to reach a specific bound.
1. Two Sum (LeetCode 1) · Easy. Find two indices whose values add to a target. Teaches the brute-force-to-hash-map step: to , and why that trade costs space.
Hint
For each element, what single value would complete the pair, and how fast can you check whether you have seen it?
2. Contains Duplicate II (LeetCode 219) · Easy. Decide whether two equal values occur within distance of each other. Teaches bounding auxiliary space by a window, instead of , and the "amortized loop" pattern of adding one and removing one per step.
Hint
Keep a set of the last values. What gets added and what gets removed each step?
Solution
from collections import Counter
def contains_nearby_duplicate(nums: list[int], k: int) -> bool:
"""Sliding window of the last k values in a set: O(n) time, O(k) space."""
window: set[int] = set()
for i, x in enumerate(nums):
if x in window:
return True
window.add(x)
if i >= k:
window.discard(nums[i - k])
return False
assert contains_nearby_duplicate([1, 2, 3, 1], 3) is True
assert contains_nearby_duplicate([1, 0, 1, 1], 1) is True
assert contains_nearby_duplicate([1, 2, 3, 1, 2, 3], 2) is False
def top_k_frequent(nums: list[int], k: int) -> list[int]:
"""Bucket by frequency: O(n) instead of O(n log n) from sorting."""
freq = Counter(nums)
buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]
for x, c in freq.items():
buckets[c].append(x)
out: list[int] = []
for c in range(len(nums), 0, -1):
for x in buckets[c]:
out.append(x)
if len(out) == k:
return out
return out
assert sorted(top_k_frequent([1, 1, 1, 2, 2, 3], 2)) == [1, 2]
assert top_k_frequent([1], 1) == [1]
print("ok")
Time , space for the window problem. The second function is the solution to problem 5 below: time and space via bucket sort on frequencies, beating the heap approach.
3. Sort Colors (LeetCode 75) · Medium. Sort an array containing only the values 0, 1 and 2, in place. Teaches that the sorting bound is for comparison sorting of arbitrary keys; with three distinct values one pass and space suffice.
Hint
Counting sort works in two passes. Can you do it in one with three pointers (the Dutch national flag partition)?
Solution
def sort_colors(nums: list[int]) -> None:
"""Dutch national flag: one pass, O(1) space."""
lo, i, hi = 0, 0, len(nums) - 1
while i <= hi:
if nums[i] == 0:
nums[lo], nums[i] = nums[i], nums[lo]; lo += 1; i += 1
elif nums[i] == 2:
nums[hi], nums[i] = nums[i], nums[hi]; hi -= 1
else:
i += 1
import random
for _ in range(300):
a = [random.randint(0, 2) for _ in range(random.randint(0, 10))]
b = a[:]; sort_colors(b)
assert b == sorted(a), (a, b)
print("ok")
time: each iteration either advances i or decrements hi, so hi - i shrinks by one every step. auxiliary space.
4. Maximum Subarray (LeetCode 53) · Medium. Find the contiguous subarray with the largest sum. Teaches a three-rung ladder: (all subarrays, sum each), (running sums), (Kadane). Also a divide-and-conquer solution worth doing for the Master theorem practice.
Hint
For each end index, what is the best subarray ending exactly there, and how does it relate to the best one ending one index earlier?
Solution
def max_subarray_kadane(nums: list[int]) -> int:
"""O(n) instead of the O(n^2) all-subarrays scan or O(n^3) naive sum."""
best = cur = nums[0]
for x in nums[1:]:
cur = max(x, cur + x)
best = max(best, cur)
return best
def max_subarray_brute(nums: list[int]) -> int:
n = len(nums)
return max(sum(nums[i:j + 1]) for i in range(n) for j in range(i, n))
import random
assert max_subarray_kadane([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
assert max_subarray_kadane([-3, -1, -2]) == -1
for _ in range(300):
a = [random.randint(-9, 9) for _ in range(random.randint(1, 9))]
assert max_subarray_kadane(a) == max_subarray_brute(a), a
print("ok")
time, space. The brute force is kept as a comparator, a technique from Testing & Debugging Algorithms.
5. Top K Frequent Elements (LeetCode 347) · Medium. Return the most frequent values. The statement demands better than ; teaches heap (), quickselect ( expected) and bucket sort () as three answers to the same constraint. Solution is included under problem 2 above.
Hint
Frequencies are integers between 1 and . What sorts integers in a bounded range in linear time?
6. Kth Largest Element in an Array (LeetCode 215) · Medium. Find the -th largest value without fully sorting. Teaches the difference between (sort), (heap) and expected (quickselect), and why "expected" is the right word.
Hint
Quicksort's partition puts the pivot in its final position. Which side do you need to recurse into?
Solution
# Kth largest via quickselect (expected O(n))
import random
def kth_largest(nums: list[int], k: int) -> int:
target = len(nums) - k # index in ascending order
lo, hi = 0, len(nums) - 1
while True:
pivot = nums[random.randint(lo, hi)]
i, lt, gt = lo, lo, hi # three-way partition: [lo,lt) < p, [lt,gt] == p, (gt,hi] > p
while i <= gt:
if nums[i] < pivot:
nums[i], nums[lt] = nums[lt], nums[i]; i += 1; lt += 1
elif nums[i] > pivot:
nums[i], nums[gt] = nums[gt], nums[i]; gt -= 1
else:
i += 1
if target < lt:
hi = lt - 1
elif target > gt:
lo = gt + 1
else:
return pivot
assert kth_largest([3, 2, 1, 5, 6, 4], 2) == 5
assert kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) == 4
for _ in range(200):
a = [random.randint(-5, 5) for _ in range(random.randint(1, 12))]
k = random.randint(1, len(a))
assert kth_largest(a[:], k) == sorted(a)[-k]
print("ok")
Expected : the recurrence is in expectation, Master case 3. Worst case with adversarial pivots; the random pivot makes that worst case hold only with negligible probability for every input. The three-way partition keeps duplicates from degrading it. Median-of-medians gives a deterministic with a worse constant.
7. Static Range Sum Queries (CSES 1646) · Easy. Answer sum-over-range queries on a fixed array. Teaches the two-parameter bound: naive versus with prefix sums, and why with the naive one is steps.
Hint
If you knew the sum of the first elements and the sum of the first , what is the sum of ?
8. Distinct Numbers (CSES 1621) · Easy. Count distinct values in an array of . Teaches the practical gap between (compare all pairs), (sort and count runs) and expected (hash set), and, if you try it in Python, the constant-factor gap between a set and a sort.
Hint
Sort, then count positions where the value changes. Or insert everything into a set and take its size.
9. Theatre Square (Codeforces 1A) · Easy. Cover an rectangle with tiles using the fewest tiles. Teaches that simulation is and the answer is arithmetic, plus a 64-bit overflow trap ().
Hint
How many tiles along each side, rounded up? Multiply, and make sure the product fits.
10. Number of Ways (Codeforces 466C) · Medium. Count ways to split an array into three contiguous parts with equal sums. Teaches turning an two-cut enumeration into with prefix sums and a running count, the single most common TLE-to-AC transformation in contests.
Hint
The total must be divisible by 3. Scan once, counting prefixes equal to one third so far; each time the prefix equals two thirds, add that count.
Common mistakes & interview follow-ups
How to state a complexity in an interview. Say the resource, the case, the parameters and the bound, and then the one-sentence reason: "Time is worst case because of the sort; everything after it is a single pass. Auxiliary space is for the hash map; if we are allowed to sort in place and use two pointers instead, it drops to ." That is the complete form. Then stop and let the interviewer follow up.
The follow-ups you should expect, with the short answers:
- "Can you do better?" Compare against the lower bound. If you are at and the problem requires reading all input, say so: "No: any correct algorithm must read every element, so is a lower bound and we are at ." If you are at because of a sort, ask whether the keys have structure (small integers, bounded range) that permits counting or radix sort.
- "Is that worst case or average?" Know which you have. Hash-based: expected. Quickselect: expected. Sorting with Timsort: worst case. If you have an expected bound, mention the worst case and how likely it is.
- "What if is / the data does not fit in memory?" Move from space to streaming or space, or to external-memory thinking: process in blocks, sort by chunks and merge. Any solution that needs the whole input in a hash map needs redesign.
- "What is the complexity of that library call?" Know your language's table.
sortis ;heapq.heappushis ;list.pop(0)is ;str.joinis ;Collections.sortis ;ArrayList.remove(int)is ;TreeMap.getis . - "What is the space, including the stack?" Count recursion depth. If your DFS is recursive, say for the stack and name the worst case .
- "What dominates for small ?" Constants. An insertion sort beats merge sort for below about 20–50, which is why library sorts switch to it for small runs.
- "This is amortized O(1); what is the worst single operation?" for a dynamic array resize or a hash table rehash. If the interviewer cares about tail latency, propose incremental resizing.
The mistakes interviewers see most: forgetting the cost of a sort buried in a helper; claiming space while recursing; saying for a nested loop because "the inner loop is small"; confusing (a parameter) with a constant; and, most of all, not saying anything about complexity until asked. State it unprompted, after the brute force and again after the optimal solution.
Quick quiz
1. True or false: .
Answer
True. Upper: for . Lower: . Witnesses , , .
2. An algorithm does work and then calls itself four times on inputs of size . Complexity?
Answer
, , : case 1, . The leaves dominate.
3. A dynamic array grows by adding 100 slots each time it is full instead of doubling. Amortized cost of append?
Answer
, not . With additive growth there are resizes copying elements: a total of copies for appends, amortized. Geometric growth is essential; the aggregate argument depends on the copies forming a geometric series.
4. Which is faster for : an algorithm or an one?
Answer
and , so by a factor of 50, ignoring constants. But is sqrt decomposition's class, and its constants are often small; for the two are against , only 8× apart, and constants can close that. Compute the actual numbers rather than ranking by class alone.
5. Your hash-map solution is expected. An adversary controls the input. What is the honest bound and what do you do?
Answer
worst case if all keys collide. Mitigations: a randomised hash seed the adversary cannot predict (what Python and Ruby do), a tree-based fallback for long chains (Java 8), or switch to a balanced tree for a guaranteed .
Further reading
- CLRS, Introduction to Algorithms, 4th ed.: Chapter 3 (growth of functions and the formal definitions), Chapter 4 (divide and conquer, recursion trees, the Master theorem and its proof, Akra–Bazzi in the notes), Chapter 16 in 4e / 17 in 3e (amortized analysis: aggregate, accounting and potential methods on exactly the dynamic table, binary counter and multipop stack used here).
- Sedgewick & Wayne, Algorithms, 4th ed., Section 1.4 "Analysis of Algorithms": the doubling-ratio experiment that the harness on this page reproduces, and the tilde notation for constants.
- Skiena, The Algorithm Design Manual, 3rd ed., Chapter 2: the dominance table and the "what fits in a second" discussion.
- Knuth, "Big Omicron and Big Omega and Big Theta", SIGACT News 8(2), 1976: where the conventions were fixed.
- Tarjan, "Amortized Computational Complexity", SIAM Journal on Algebraic and Discrete Methods 6(2), 1985: the paper that named amortized analysis and introduced the potential method.
- Akra & Bazzi, "On the Solution of Linear Recurrence Equations", Computational Optimization and Applications 10, 1998.
- cp-algorithms: Big-O notation and complexity is referenced throughout the site's problem pages; the site's per-algorithm complexity statements are a good source of worked recurrences.
- Cloudflare blog, "Details of the Cloudflare outage on July 2, 2019": a production post-mortem written as a complexity analysis.
- Klink & Wälde, "Efficient Denial of Service Attacks on Web Application Platforms", 28C3, 2011: the hash-flooding talk.
Where to go next
Previous: How to Use This Course & Study Plan Overview · Next: Recursion & Mathematical Induction, which supplies the proof technique behind every recurrence on this page, and then How Data Structures Live in Memory for the constants.
Related: Your Language's Data Structures (the per-operation cost tables), Hash Tables & Hashing in Depth (expected versus worst case in practice), Sorting & Searching (the lower bound), Module 0 · Foundations.