Data Structures & Algorithms

Two programs solve the same problem on the same laptop. One answers in forty milliseconds; the other is still running when you go home. Nothing in the source code makes the gap obvious, and no amount of faster hardware closes it. The gap is asymptotic complexity, and learning to see it in code you have not run yet is the most valuable habit this course will give you.

The big picture

This whole course is about a single practical skill: choosing the right steps and the right container so a program finishes in a reasonable time. The steps are the algorithm; the container is the data structure. The reason it matters is scale: on ten items almost anything works, but on ten million items a poor choice can turn one second into a week.

In this first lesson we answer a question that has to come before any code: how do we even measure whether one approach is better than another? The surprising answer is that we do not time it with a stopwatch. We count work as the input grows.

Numbers make the stakes concrete. Assume one basic operation costs a nanosecond, so the machine performs roughly a billion of them each second. Here is the wall-clock cost of three growth rates at three input sizes:

n               n ops        n*log2(n) ops     n^2 ops
-------------------------------------------------------------
1,000           1 us            10 us          1 ms
1,000,000       1 ms            20 ms          about 17 minutes
1,000,000,000   1 s             30 s           about 32 years

Read the bottom row slowly. At a billion items the linear method finishes before you look up, and the quadratic method outlives your career. Notice too that n*log2(n) sits far closer to n than to n^2: the logarithm grows so slowly that an n*log2(n) algorithm is, for every practical input, a linear algorithm with a modest tax. That explains why so much of this course is spent turning quadratic solutions into n*log2(n) ones.

Key idea: hardware buys a constant factor, but a better growth rate buys orders of magnitude, and only the growth rate keeps paying as the data gets larger.

What an algorithm and a data structure are

An algorithm is a precise, finite sequence of steps that solves a problem. Think of it as a recipe: a fixed list of instructions that, followed exactly, always produces the dish. A data structure is a way of organizing data in memory so those steps can run efficiently, like the difference between a shoebox of loose receipts and a labeled filing cabinet. The same problem can be solved by many algorithms over many structures, and the choice can mean the difference between an answer in a second and an answer in a week.

Key idea: an algorithm is the recipe, a data structure is how the ingredients are organized, and pairing them well is what makes code fast.

The pairing matters more than beginners expect. "Find every duplicate in a list" is the same problem whether you scan the list once per item, touching roughly n^2 pairs, or drop every item into a hash set as you go, touching each item once. Same problem, same machine; the difference lives entirely in which container you reached for.

Why not just time it with a stopwatch?

Timing a program with a stopwatch is tempting but unreliable. The seconds you measure depend on your CPU, the language, what else the machine is doing, and the exact input you happened to pick. Run the same code on a friend's laptop and you get a different number.

Instead we count basic operations - one small unit of work such as a comparison, an assignment, or an arithmetic step - as a function of the input size, almost always called n. This gives a machine-independent measure that predicts how the cost grows, which is what matters at scale.

The formal name for this assumption is the RAM model (random access machine): reading or writing any memory cell, comparing two values, and doing one arithmetic step each cost one unit, wherever the data sits. Real hardware does not obey this, because a value already in the CPU cache arrives roughly a hundred times faster than one from main memory. The model is still worth adopting because it preserves the ranking, and where it breaks down - as it does for cache-hostile structures like linked lists - we will say so.

Two habits keep the counting honest. Decide what n means before you count: characters for a string, a pair (V vertices, E edges) for a graph. And decide which operation you are counting - comparisons for sorting, probes for a hash table.

Key idea: counting operations as a function of n is portable and predictive; wall-clock seconds are neither. Timing still has a role, but it comes last, to check a decision you already made by counting.

Best, worst, and average case

The same algorithm can do different amounts of work on inputs of the same size. Consider a linear search: scanning n items one by one for a target value.

• Best case: the target is the first item, so you stop after one comparison.
• Worst case: the target is last or absent, so you make n comparisons.
• Average case: over random positions, about n/2 comparisons.

We care most about the worst case, because it is a guarantee: the algorithm will never be slower than that, no matter how unlucky the input. Occasionally we also study the average case, when the worst case is rare and would paint an unfairly gloomy picture.

The "about n/2" deserves an argument rather than a hand wave. Assume the target appears exactly once and is equally likely in any of the n positions. Finding it at position i costs i comparisons, so the expected cost is the average of 1 through n:

E[comparisons] = (1 + 2 + 3 + ... + n) / n
               = [ n(n + 1) / 2 ] / n
               = (n + 1) / 2

For n = 100 that is 50.5 comparisons. Note what the derivation depended on: every position being equally likely. Change that assumption and the answer changes. If the wanted item is usually near the front - common in real systems, where recently used items get looked up again - the average falls well below n/2 while the worst case is unchanged. An average-case claim is only as trustworthy as its stated input distribution; a worst case assumes nothing, which is why it is the number you can put in a contract.

A fourth case is worth naming now. Amortized cost is the average cost per operation across a long sequence, in the worst case for that sequence - not a probabilistic average. When Lesson 4 calls appending to a dynamic array amortized O(1), it means any sequence of n appends costs O(n) total, guaranteed, even though one individual append occasionally costs O(n) by itself.

Key idea: the worst case is the promise you can make to a user, so it is the case we analyze first; average case needs an input distribution, and amortized cost is a worst-case guarantee spread over a sequence.

Worked example: counting comparisons in a linear search

Take the concrete list data = [7, 3, 9, 4, 1, 8], so n = 6, and search for the value 4. The loop compares one item per pass and stops at the first match. Track the state after each pass:

pass  i   data[i]   data[i] == 4 ?   comparisons so far
  1   0      7           no                 1
  2   1      3           no                 2
  3   2      9           no                 3
  4   3      4           YES                4   -> return 3

Four comparisons, and the loop never touched positions 4 or 5. Now change the target and re-count without rerunning anything. Searching for 7 costs 1 comparison, the best case. Searching for 8 costs 6, and searching for 5 - which is absent - also costs 6, because the loop must exhaust the list before it can declare failure. A failed search always hits the worst case, so if your workload is mostly misses, average and worst are the same number.

Now count once more in the style we will use all course. Per pass the loop does one index increment, one bounds check, one array read, and one comparison: four operations. Outside the loop, two of setup and one to return. Total: 4k + 3, where k is the pass on which we stop and k ranges from 1 to n. The worst case is 4n + 3. Big-O will collapse all of that to O(n) next lesson - but the collapse is a deliberate simplification of a count we could produce exactly, not a shrug.

Key idea: trace a small input by hand before trusting any complexity claim; the trace tells you what the loop really does, and the formula falls out of it.

A first look at growth

Here is a loop that sums the numbers from 0 to n minus 1. It does a fixed amount of setup, then a chunk of work once per item.

def total(n):
    s = 0                 # 1 operation
    for i in range(n):    # runs n times
        s = s + i         # 1 operation each time
    return s              # 1 operation

Count it. The line s = 0 runs once, the return runs once, and the body runs n times, so the total is about n + 2 operations: 7 for n = 5, about 1002 for n = 1000. As n grows, the fixed "+2" stops mattering and what dominates is that the cost is proportional to n. Naming exactly that, while deliberately ignoring the details that do not matter at scale, is the job of Big-O notation.

Key idea: for large inputs only the fastest-growing part of the operation count matters, and that is what we will learn to name.

When a slow algorithm is the right answer

Complexity analysis is a tool for deciding, not a moral code. Three situations make the quadratic solution genuinely correct. When n is small and bounded: sorting five table columns with an n^2 method costs 25 comparisons, and the clever method spends more on setup than it saves - which is why production sort libraries fall back to insertion sort on small runs. When the code runs once: a nightly script taking four minutes instead of forty seconds is not worth an afternoon. And when the simple version is the one you can prove correct, because a correct n^2 program beats a subtly broken n*log(n) one every day.

The judgement call is about where n can go, not where it is today. The bug that takes down a service is almost always a quadratic loop written when the table held 200 rows and discovered when it holds 200,000.

Key idea: analyze first, then choose; O(n^2) is a defensible decision when n is small and bounded, and a time bomb when it is not.

Where people get stuck

• "A faster computer fixes a slow algorithm." Better hardware multiplies speed by a constant, but a worse growth rate always wins as n increases. Doubling your CPU speed does not help if the work grows as n squared: it buys you an input 1.41 times larger, once.
• "Fewer lines of code means faster." Line count is unrelated to running time. A short line inside a loop that runs a million times costs far more than a long line that runs once. A one-line list comprehension containing a membership test against a list is quietly quadratic.
• "We should always optimize for the best case." The best case is a lucky accident you cannot rely on. Guarantees come from the worst case. Best case is useful mainly as a sanity check: if it is already too slow, redesign.
• "n means seconds." No. n is the size of the input, such as the number of items; it is not a unit of time. Nor is it the value of the input: a loop running n times, where n is a number you were handed, is exponential in the number of digits of that number.
• "My benchmark disagreed, so the analysis is wrong." Usually the benchmark is too small. Two curves with different growth rates can cross well past the sizes you tested, and constant factors dominate below the crossover. Time several sizes and look at the shape, not one number.

Recap

• An algorithm is a finite recipe of steps; a data structure organizes data so those steps run efficiently, and the pairing usually matters more than the code style.
• We measure cost by counting basic operations as a function of input size n, because operation counts are machine-independent and predict behaviour at scales you have not tested.
• The RAM model treats every memory access and arithmetic step as one unit; it is an approximation that preserves the ranking of algorithms.
• Worst case is a guarantee, average case needs a stated input distribution, and amortized cost is a worst-case guarantee spread across a sequence.
• The average cost of a successful linear search is (n + 1) / 2, derived from summing 1 through n; a failed search always costs the full n.
• For large n only the fastest-growing term matters, which sets up Big-O notation in the next lesson.

Before you write code, ask what n is, what one operation is, and how the count grows. Three questions, thirty seconds, and no other habit in software repays the time so well.

Sources

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). The role of algorithms in computing; Getting started. In Introduction to algorithms (4th ed., chs. 1-2). MIT Press. find source ↗
2. Sedgewick, R., & Wayne, K. (2011). Analysis of algorithms. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
3. Demaine, E., Ku, J., & Solomon, J. (2020). Lecture 1: Algorithms and computation. 6.006 Introduction to Algorithms, MIT OpenCourseWare. ocw.mit.edu
4. Morin, P. (2013). Introduction. In Open data structures (ch. 1). opendatastructures.org
5. Malan, D. J. (2025). Lecture 3: Algorithms. CS50x, Harvard University. cs50.harvard.edu
6. Sedgewick, R., & Wayne, K. (2011). Programming model. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
7. Python Software Foundation. (n.d.). timeit - Measure execution time of small code snippets. Python 3 documentation. docs.python.org

The big picture

Say "quadratic" to any working programmer and they will wince before you finish the sentence. Big-O is the shared vocabulary that lets one word carry that much information. It is not advanced mathematics dressed up to intimidate beginners; it is a compression scheme for operation counts, designed to throw away exactly the details that do not survive a change of machine.

The big picture

In the last lesson we counted operations and noticed that for large inputs only the fastest-growing part matters. Big-O notation is the vocabulary for that idea. It lets us describe the shape of an algorithm's growth in a few symbols, so we can compare two approaches at a glance without knowing the exact machine or instruction count.

Here we define Big-O and its two siblings, learn two simplification rules, and memorize a short ladder of growth classes you will use for the rest of the course.

What Big-O means

Big-O notation describes an upper bound on how the running time (or memory) of an algorithm grows as the input size n grows. When we say an algorithm is O(n), we mean that beyond some input size its cost grows no faster than a constant times n. A helpful analogy: Big-O is like describing how a recipe scales when the number of dinner guests doubles. Some recipes take twice as long (linear), some take four times as long (quadratic), and some barely change (constant). Big-O names that scaling behavior and throws away the exact minutes.

The precise definition is short and worth learning, because every simplification rule below is a consequence of it:

f(n) = O(g(n))  if there exist positive constants c and n0
                such that  0 <= f(n) <= c * g(n)  for all n >= n0

Two escape hatches do all the work. The constant c lets you scale g upward as much as you like, which is what kills constant factors. The threshold n0 lets you ignore small inputs entirely, which is what kills lower-order terms - they only ever win when n is small. Read the definition as a promise: "past some point, and up to some fixed multiple, f never exceeds g."

Key idea: Big-O captures how cost grows with input size, ignoring machine-specific constants so we compare the shape of growth, not the raw speed.

Two simplification rules

To turn a detailed operation count into a Big-O class, apply two rules in order:

1. Drop constant factors. 5n and 100n are both O(n). The constant depends on the machine and the language, which is exactly the detail Big-O sets aside.
2. Drop lower-order terms. In n^2 + n + 7, the n^2 term dwarfs the others once n is large, so the whole expression is O(n^2). At n = 1000, n^2 is a million while n + 7 is about a thousand, a rounding error by comparison.

Both rules are theorems, not conventions, and you can prove them from the definition in two lines. Take f(n) = 3n^2 + 5n + 2 and claim it is O(n^2). For every n >= 1 we have n <= n^2 and 1 <= n^2, so:

3n^2 + 5n + 2  <=  3n^2 + 5n^2 + 2n^2  =  10n^2      for all n >= 1
so the definition holds with c = 10 and n0 = 1.

The same f is also Omega(n^2), since 3n^2 + 5n + 2 >= 3n^2 for every n >= 0 - take c = 3. Bounded above and below by multiples of n^2, it is Theta(n^2), and that is the honest, tight answer.

One warning the definition makes obvious. Because Big-O is only an upper bound, 3n^2 + 5n + 2 = O(n^3) is a perfectly true statement, and so is O(n^100). True, useless, and the reason "what is the Big-O?" really means "what is the smallest upper bound you can defend?"

Key idea: keep only the single fastest-growing term and drop its constant coefficient - and remember that a loose upper bound is technically correct but professionally worthless.

The common growth classes

From slowest-growing (best) to fastest-growing (worst), the classes you will meet all course are:

Big-O	Name	Example
O(1)	Constant	Array index lookup
O(log n)	Logarithmic	Binary search
O(n)	Linear	Scanning a list once
O(n log n)	Linearithmic	Merge sort, quicksort average
O(n^2)	Quadratic	Bubble, insertion, selection sort
O(2^n)	Exponential	Naive subset enumeration

A concrete feel for the gap: at n = 1,000,000, an O(n) algorithm does about a million steps, an O(log n) algorithm does about 20, and an O(n^2) algorithm does a trillion. The class you land in usually matters far more than any clever constant-factor tuning.

The logarithm surprises people, so pin it down. Base-2 logarithms count halvings: log2(1,000) is about 10, log2(1,000,000) is about 20, log2(1,000,000,000) is about 30. Every thousandfold increase in n adds ten steps. That is why binary search on a billion sorted records is a handful of probes, and why an O(log n) operation can be treated as effectively free.

Key idea: the growth class you fall into dominates performance at scale; memorize the ladder from O(1) up to O(2 to the n).

Reading complexity off a loop

You rarely need the formal definition in daily work. You need to look at nested code and see the exponent. Five patterns cover most of what you will meet:

PATTERN                                     ITERATIONS      CLASS
for i in range(n): ...                          n           O(n)

for i in range(n):                            n * n         O(n^2)
    for j in range(n): ...

for i in range(n):                          n(n+1)/2        O(n^2)
    for j in range(i, n): ...

i = n                                       log2(n)         O(log n)
while i > 1: i = i // 2

for i in range(n):                          n * log2(n)     O(n log n)
    j = n
    while j > 1: j = j // 2

Two composition rules generate all of them. Sequential blocks add: a loop of n followed by a loop of n^2 costs n + n^2, which is O(n^2). Nested blocks multiply: an inner loop costing n, run n times, costs n^2.

The third pattern is the one people get wrong. The inner loop runs n times when i = 0, n - 1 times when i = 1, and so on down to 1, so the total is n + (n-1) + ... + 1 = n(n+1)/2. That is half of n^2 plus a linear term - still Theta(n^2), because the constant 1/2 disappears. "It only does half the work" does not change the class, though it does halve the wall clock, which is why this pattern shows up in real code.

The fourth pattern is the source of every logarithm in this course. Starting at n and halving until you reach 1 takes log2(n) steps, because after k halvings the value is n / 2^k, and that hits 1 when k = log2(n). For n = 16 the sequence is 16, 8, 4, 2, 1 - four halvings, and log2(16) = 4.

Key idea: sequential code adds, nested code multiplies, and repeated halving gives a logarithm; almost every analysis is those three facts applied in sequence.

Not just an upper bound: Omega and Theta

Two related symbols make the picture precise. Big-Omega (written with the Greek letter Omega) is a lower bound: the cost grows at least this fast. Big-Theta (the Greek letter Theta) is a tight bound: the cost grows exactly this fast, squeezed from both above and below. If an algorithm is both O(n) and Omega(n), then it is Theta(n). A speed-limit analogy: Big-O is "no faster than 60," Big-Omega is "no slower than 60," and Big-Theta is "exactly 60." In casual use people say "O" when they really mean a tight bound, but knowing the difference keeps your reasoning honest.

Omega earns its keep when we talk about problems rather than programs. Any comparison-based sorting algorithm must make Omega(n log n) comparisons in the worst case - a proof about every possible algorithm, not about one implementation. That is a statement no amount of cleverness can beat, and it is why merge sort is considered optimal rather than merely good. Lower bounds tell you when to stop looking for a faster method.

Key idea: Big-O is an upper bound, Big-Omega a lower bound, and Big-Theta a matching bound that pins the growth from both sides; lower bounds are claims about problems, not implementations.

Worked example: a nested loop

Consider two loops, one inside the other:

def count_pairs(items):
    c = 0
    for i in items:        # n times
        for j in items:    # n times, for each i
            c = c + 1      # runs n * n times total
    return c

Trace the work. For each of the n outer passes, the inner loop runs n times, so the body executes n * n = n^2 times.

This algorithm is O(n^2). If we added a separate single loop before it, the total would be n^2 + n, which simplifies back to O(n^2) by dropping the lower-order term. The tell-tale sign of O(n^2) is a loop nested directly inside another loop, both running over the input.

Confirm it empirically on tiny inputs, where you can count by hand. With items = [4, 7, 1], n = 3: the outer loop takes i = 4, then 7, then 1, and for each the inner loop runs over all three items. The counter c reaches 3 after the first outer pass, 6 after the second, 9 after the third - exactly n^2 = 9. Double n to 6 and the count becomes 36, four times as much for twice the input. That factor-of-four response to a doubling is quadratic growth, and it is the cheapest experiment you can run to check any complexity claim: double n, and see whether the work grows by 2x (linear), a bit over 2x (n log n), or 4x (quadratic).

Key idea: a loop nested inside a loop over the same input is the classic signature of O(n squared), and doubling n is the fastest way to confirm a growth class experimentally.

Where people get stuck

• "O(2n) is worse than O(n)." They are identical. The constant 2 is dropped, so both are O(n). Writing O(2n) is not wrong, just redundant, like saying "an even number divisible by two."
• "Big-O tells you the exact running time." It only tells you the growth shape. Two O(n) algorithms can differ by a large constant factor in practice, and below the crossover point the "worse" class often wins - which is exactly why real sorting libraries switch to insertion sort on short runs.
• "Big-O always means the worst case." Big-O is just an upper bound on a chosen scenario; you can state Big-O for the best, average, or worst case. People often apply it to the worst case, but the notation itself is separate from the case. "Quicksort is O(n log n) on average and O(n^2) in the worst case" is a well-formed sentence.
• "O(log n) needs a base." The base only changes the answer by a constant factor, since log_a(n) = log_b(n) / log_b(a), so it is dropped. Inside an exponent the base does matter: O(2^n) and O(3^n) are genuinely different.
• "There is always one variable." Graph algorithms are routinely O(V + E) in two independent quantities, and matrix code is often O(r * c). Collapsing them to a single n loses information, and sometimes the answer.
• "Dropping constants means constants do not matter." They matter enormously to your users; they just do not affect the classification. Choose the class first, then optimize the constant inside it.

Recap

• Big-O is an upper bound on growth; formally f(n) = O(g(n)) when f(n) <= c*g(n) for all n beyond some threshold n0.
• The constant c is what lets us drop constant factors, and the threshold n0 is what lets us drop lower-order terms.
• Big-Omega is a lower bound and Big-Theta is a tight bound; O and Omega together give Theta, and Theta is the answer worth quoting.
• Know the ladder: O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n), from best to worst.
• Sequential code adds, nested code multiplies, and repeated halving yields log2(n); a triangular nested loop is n(n+1)/2, still Theta(n^2).
• A loose upper bound such as "n^2 is O(n^100)" is true and useless; always quote the tightest bound you can justify.

From here on, every structure and algorithm in the course arrives with a Big-O label. Treat the label as a claim you could re-derive from a loop count, not a fact to memorize.

Sources

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Characterizing running times. In Introduction to algorithms (4th ed., ch. 3). MIT Press. find source ↗
2. Sedgewick, R., & Wayne, K. (2011). Analysis of algorithms. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
3. Demaine, E., Ku, J., & Solomon, J. (2020). Lecture notes. 6.006 Introduction to Algorithms, MIT OpenCourseWare. ocw.mit.edu
4. Morin, P. (2013). Introduction: The model of computation and correctness, running time, and space. In Open data structures (ch. 1). opendatastructures.org
5. Demaine, E., & Devadas, S. (2015). Lecture notes. 6.046J Design and Analysis of Algorithms, MIT OpenCourseWare. ocw.mit.edu
6. Rowell, E. (n.d.). Big-O algorithm complexity cheat sheet. bigocheatsheet.com
7. Python Software Foundation. (n.d.). TimeComplexity. Python Wiki. wiki.python.org

The big picture

An algorithm that is asymptotically perfect and needs 200 GB of scratch space is not a solution. Memory is the constraint that fails loudly - a MemoryError, an out-of-memory kill, a machine that starts swapping and drops to a hundredth of its speed - and it is the one most often left out of the analysis.

The big picture

Running time is only half the story. A program that is fast but needs more memory than the machine has will still crash. Space complexity is the memory counterpart of time complexity: it measures how much memory an algorithm needs as the input grows, again expressed in Big-O.

This lesson shows how to count extra memory, why recursion quietly consumes memory, and how you can often trade one resource for the other.

Before the abstraction, some real numbers, measured on a 64-bit CPython build. They are worth knowing because they set the constants hidden inside every O(n) you will write:

sys.getsizeof([])                    ->     56 bytes  (empty list header)
sys.getsizeof(list(range(1000)))     ->  8,056 bytes  (56 + 8 per pointer)
sys.getsizeof(1000)                  ->     28 bytes  (one int OBJECT)
sys.getsizeof(array.array('q', ...)) ->  8,320 bytes  (1000 raw 64-bit ints)

A Python list of a million distinct integers therefore costs about 8 MB of pointers plus about 28 MB of integer objects, roughly 36 MB. The same million values in an array('q') cost 8 MB, and in a NumPy int64 array the same 8 MB. All three are O(n) space. The constant factor between them is four and a half, which is the difference between fitting in cache and not.

Key idea: Big-O hides a constant factor that in memory is often 4x or more; state the class, then check the actual bytes when n is large.

What space complexity measures

Space complexity is how much memory an algorithm needs as a function of the input size n. We usually care about auxiliary space: the extra memory an algorithm uses beyond the input it was handed. The analogy is a cook's countertop: the ingredients (the input) are already there, and auxiliary space is the extra counter room the recipe needs for mixing bowls and prep. A recipe that dirties one bowl regardless of guest count uses constant extra space; one that needs a fresh bowl per guest uses linear extra space.

Key idea: auxiliary space is the extra memory beyond the input, and like time it is described with Big-O.

Counting extra memory

Compare two ways to double every number in a list. The first modifies the list in place; the second builds a brand new list.

def double_in_place(a):
    for i in range(len(a)):
        a[i] = a[i] * 2      # no new list; O(1) extra space

def double_copy(a):
    result = []
    for x in a:
        result.append(x * 2) # new list of size n; O(n) extra space
    return result

Both do O(n) work in time, since each visits n elements once.

But the memory differs. double_in_place uses only a fixed handful of extra variables (the loop index i), so its auxiliary space is O(1). An algorithm like this that transforms its input using only O(1) extra memory is called in-place. By contrast, double_copy allocates a new list of n items, so its auxiliary space is O(n).

Here is the reference table for the algorithms in this course. Read the middle column as auxiliary space, and note how often the answer is driven by recursion depth rather than by any array:

ALGORITHM              AUXILIARY SPACE   WHY
insertion / bubble         O(1)          a few index variables
selection sort             O(1)          swaps in place
heapsort                   O(1)          heap lives inside the array
quicksort                  O(log n)      recursion stack, recursing on
                                         the smaller side first
merge sort (arrays)        O(n)          a scratch array to merge into
merge sort (linked list)   O(log n)      relinks nodes, stack only
binary search, iterative   O(1)          two index variables
binary search, recursive   O(log n)      one frame per halving
BFS / DFS on a graph       O(V)          visited set plus queue or stack
hash table with n keys     O(n)          the table itself

Two rows deserve a second look. Merge sort on an array needs a scratch buffer, but merge sort on a linked list does not, because merging is just pointer surgery - the same algorithm has different space complexity on different structures. And iterative binary search is O(1) while the recursive version is O(log n), a difference that comes purely from the call stack. Neither fact is visible from the pseudocode alone.

Key idea: modifying data in place costs O(1) extra memory; building a new collection of size n costs O(n); and the same algorithm can change space class when you change the underlying structure.

Recursion costs space too

Memory is not only the data structures you name. Every pending function call occupies a frame on the call stack, the region of memory that holds one frame per active, not-yet-returned function call. Think of it as a stack of sticky notes: each call you have not finished leaves a note on the pile, and the notes are removed only as calls return.

A recursion that goes n levels deep before any call returns keeps n frames alive at once, so it uses O(n) space on the stack even if it creates no arrays or lists. We will see this clearly with recursive sorts, where the recursion depth drives the space bound.

The limit is not theoretical. CPython caps recursion at 1000 frames by default (sys.getrecursionlimit()) and raises RecursionError beyond it, precisely so a runaway recursion fails with a traceback instead of corrupting the C stack. That means a recursive routine whose depth is proportional to n will die on a 5000-element list, while one whose depth is proportional to log2(n) survives inputs larger than the machine's memory: log2 of a trillion is only 40. Depth O(log n) is safe forever; depth O(n) is a bug waiting for a big input.

Key idea: recursion consumes stack memory proportional to its maximum depth, even when it allocates no data structures - and O(n) depth will hit a hard limit long before O(log n) depth does.

The time-space trade-off

Often you can spend memory to save time, or the reverse. A classic example is memoization: caching results you have already computed so you never recompute them. Storing those answers uses extra space but avoids repeated work, turning some painfully slow recursions into fast ones.

Consider computing Fibonacci numbers. The naive recursion recomputes the same subproblems exponentially many times. A memo table of size n stores each answer once, cutting the time from exponential to linear at the cost of O(n) extra memory. That is the trade-off in miniature: a little more space bought a great deal of time.

Choosing the right point on that trade-off is a core engineering judgment, and stating both the time and space complexity of your solution is how you make the trade-off visible to yourself and others.

The exchange runs in both directions, which is easy to forget. Compression spends CPU time to save bytes. A Bloom filter spends a small chance of false positives to store a membership test in a few bits per key instead of the whole key. Recomputing a value instead of caching it is a legitimate optimization when memory is the binding constraint and the value is cheap. The question is never "which resource is more important" but "which one runs out first on this machine, at this n".

Key idea: memory and time can often be exchanged in either direction; memoization spends O(n) space to save exponential time, compression spends time to save space, and good engineers state both costs.

Worked example: three ways to compute Fibonacci

Take fib(5) = 5, with fib(0) = 0 and fib(1) = 1. The naive recursion builds this call tree:

                     fib(5)
              /                  \
          fib(4)                 fib(3)
        /       \               /      \
    fib(3)     fib(2)       fib(2)    fib(1)
    /    \     /    \       /    \
 fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
 /    \
fib(1) fib(0)

Count the nodes: fib(5) once, fib(4) once, fib(3) twice, fib(2) three times, fib(1) five times, fib(0) three times - 15 calls to produce one small number. The counts are themselves Fibonacci numbers, which is the tell: the number of calls for fib(n) is 2*F(n+1) - 1, growing like 1.618^n. At n = 40 that is over 300 million calls; at n = 90 it would outlast the universe.

Now the three implementations, with their costs:

def fib_naive(n):                 # TIME O(1.618^n)   SPACE O(n) stack
    if n < 2: return n
    return fib_naive(n-1) + fib_naive(n-2)

def fib_memo(n, memo=None):       # TIME O(n)         SPACE O(n) + O(n) stack
    if memo is None: memo = {}
    if n < 2: return n
    if n in memo: return memo[n]
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

def fib_iter(n):                  # TIME O(n)         SPACE O(1)
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Trace fib_iter(5) one step at a time, starting from (a, b) = (0, 1): after pass 1 it is (1, 1); pass 2, (1, 2); pass 3, (2, 3); pass 4, (3, 5); pass 5, (5, 8). Return a = 5. Correct, in five iterations and two variables.

Memoization turned exponential time into linear time by spending O(n) memory. The iterative version then gave the memory back, because computing fib(n) only ever needs the previous two values - the memo table stored n answers when the algorithm needed two. That last step is the general lesson: after you use a cache to fix the time, ask which entries you actually still need. Very often the answer is "a constant number of them", and the space collapses to O(1).

Key idea: memoize to kill repeated work, then look for the sliding window that makes the cache unnecessary.

Where people get stuck

• "Auxiliary space includes the input." No. Auxiliary space counts only the extra memory allocated, not the input already given to the function. Total space does include the input, so always say which one you mean - "in-place" is a claim about auxiliary space.
• "Recursion is free because it makes no arrays." Each pending call still holds a stack frame with its locals and return address, so deep recursion can exhaust memory on its own. CPython stops you at 1000 frames.
• "Faster always means more memory." Not always. Heapsort is in-place and beats merge sort on memory; a good algorithm often improves both. The trade-off is a common pattern, not a law.
• "Space complexity counts the number of variables in the source." It counts memory live at run time as a function of n, not how many names appear in the code. Ten scalars is still O(1).
• "A generator has the same complexity as a list." In time, roughly; in space, not at all. sum(x*x for x in data) is O(1) auxiliary space, while sum([x*x for x in data]) materializes n values first. On large inputs that single pair of brackets is the whole difference.
• "Slicing is cheap." In Python, a[1:] copies. A recursive routine that slices at each level quietly turns an O(log n) algorithm into an O(n) one in both time and space. Pass indices, not slices.

Recap

• Space complexity measures memory versus input size; auxiliary space is the extra memory beyond the input, and "in-place" means O(1) auxiliary.
• In-place algorithms use O(1) auxiliary space; building a new size-n structure uses O(n); constant factors between representations can differ by 4x or more.
• Recursion uses stack space equal to its maximum depth, so O(log n) depth is safe at any scale while O(n) depth hits CPython's 1000-frame limit.
• The same algorithm can change space class with the structure: merge sort is O(n) on arrays and O(log n) on linked lists.
• Naive Fibonacci makes 2*F(n+1) - 1 calls, growing like 1.618^n; memoization makes it O(n) time and O(n) space, and a two-variable loop makes it O(n) time and O(1) space.
• Time and space trade in both directions, so report both numbers and check which resource runs out first at your actual n.

From now on, every complexity claim in this course comes as a pair. If you only ever quote the time, you have only done half the analysis.

Sources

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Dynamic programming: Rod cutting and memoization. In Introduction to algorithms (4th ed., ch. 14). MIT Press. find source ↗
2. Sedgewick, R., & Wayne, K. (2011). Analysis of algorithms: Memory. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
3. Python Software Foundation. (n.d.). sys - System-specific parameters and functions: getsizeof and setrecursionlimit. Python 3 documentation. docs.python.org
4. Python Software Foundation. (n.d.). functools: lru_cache and cache. Python 3 documentation. docs.python.org
5. Morin, P. (2013). Introduction: The model of computation. In Open data structures (ch. 1). opendatastructures.org
6. Python Software Foundation. (n.d.). array - Efficient arrays of numeric values. Python 3 documentation. docs.python.org
7. Python Software Foundation. (n.d.). TimeComplexity. Python Wiki. wiki.python.org

The big picture

Almost everything else in this course is built on top of an array. Hash tables are arrays with a clever index function. Binary heaps are arrays pretending to be trees. Even the Python list you use without thinking is a dynamic array with a carefully tuned growth policy in C. Get the array right and the rest of the course is variations on a theme.

The big picture

The array is the most fundamental data structure and the one your computer's hardware supports most directly. Understanding why array indexing is instant, and how a resizable version stays fast, gives you the mental model behind Python lists and countless other structures built on top of arrays.

This lesson explains contiguous memory, the cost of a fixed size, and the doubling trick that makes appending to a growable array fast on average.

What an array is and why indexing is instant

An array is a block of memory holding elements of the same type in consecutive slots. Picture a row of identical mailboxes bolted together in a line and numbered from 0. Because the slots are contiguous and equally sized, the computer can jump straight to any element by arithmetic: the address of element i is the start address plus i times the element size. That single calculation, not a search, is why indexing is O(1), no matter how large the array is. Reading a[5] and a[5000000] take the same time.

Write the address rule down, because it is the whole structure in one line:

address(a[i]) = base_address + i * element_size

a = [10, 20, 30, 40]  stored as 8-byte values at base 0x1000:
index:      0       1       2       3
address: 0x1000  0x1008  0x1010  0x1018
value:      10      20      30      40

a[2] -> 0x1000 + 2 * 8 = 0x1010 -> 30      one multiply, one add

There is a second, quieter benefit that Big-O cannot see. Because the elements sit next to each other, a sequential scan is exceptionally friendly to the CPU cache. Memory arrives from RAM in cache lines of 64 bytes, so one fetch delivers eight 64-bit values, and the hardware prefetcher notices the pattern and loads the next line before you ask. Scanning an array is therefore several times faster per element than chasing pointers through scattered memory, even though both are O(n). This is the single most important reason arrays beat linked lists in practice, and we will return to it in the next lesson.

Key idea: contiguous equal-size slots let the machine compute any element's address in one step, so indexing is constant time - and the same contiguity makes scanning cache-friendly, which Big-O does not show you.

The catch: a fixed size

A classic (static) array has a fixed length chosen when it is created, like a row of mailboxes with no room to add more. To store one more element than it holds, you must allocate a bigger block and copy everything over. Inserting or deleting in the middle is also costly: every later element must shift by one slot to close or open the gap, which is O(n). Moving mailbox 999's contents down to make room at position 3 means shifting hundreds of boxes.

Key idea: a static array cannot grow cheaply, and inserting or deleting anywhere but the end forces an O(n) shift.

Dynamic arrays and the doubling trick

A dynamic array hides the fixed-size problem. Python's list is one. It keeps a larger backing block than it currently needs; the number of slots that backing block holds is its capacity, which is at least its current length. Appending is O(1) while there is spare capacity. When the block fills, the dynamic array allocates a new block, typically double the size, and copies the old elements over, which costs O(n) for that one append.

Doubling is the key trick. Because the array doubles each time it fills, those expensive copy-everything appends happen rarely and get geometrically farther apart: after copying at capacity 8, the next copy is not until 16, then 32, and so on. Averaged over a long run of appends, the cost per append works out to a constant. We call this amortized O(1): any single append might be O(n), but the average over many appends is O(1). It is like paying a large moving fee only when you outgrow your apartment, spread thinly across all the days you lived there.

a = []                 # empty dynamic array (Python list)
for i in range(1000):
    a.append(i)        # each append is amortized O(1)
print(a[500])          # O(1) index lookup

Key idea: doubling capacity makes rare O(n) resizes average out to amortized O(1) per append.

Worked example: proving amortized O(1)

"It averages out" is not an argument. Here is the counting argument. Start empty with capacity 1 and double whenever the array is full. Trace eight appends, recording capacity and how many elements get copied:

append   len  capacity before  resize?         elements copied
  1       1        1            no                   0
  2       2        1 -> 2       yes                  1
  3       3        2 -> 4       yes                  2
  4       4        4            no                   0
  5       5        4 -> 8       yes                  4
  6       6        8            no                   0
  7       7        8            no                   0
  8       8        8            no                   0
                                        total copies:  7

Seven copies for eight appends, plus the eight writes themselves: 15 operations, under 2 per append. The pattern generalizes. For n appends the copies happen at capacities 1, 2, 4, ..., n/2, and that geometric series sums to n - 1:

1 + 2 + 4 + ... + n/2  =  n - 1   <  n
total work = n writes + (n - 1) copies  <  2n
amortized cost per append = 2n / n = 2 = O(1)

Now see why the growth factor has to be multiplicative. Suppose we grew by a fixed 10 slots instead of doubling. Resizes then happen at 10, 20, 30, ..., n, and the copies sum to 10 + 20 + ... + n, which is about n^2 / 20. Divide by n appends and the amortized cost per append is n / 20 - linear, not constant. A fixed-increment growth policy turns a loop of appends into a quadratic algorithm, which is exactly the bug people write when they "optimize" memory use.

CPython does not double, incidentally. Its list_resize uses new_allocated = (newsize + (newsize >> 3) + 6) & ~3, giving the growth pattern 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ... - about 12.5 percent headroom plus a small constant. Any factor strictly greater than 1 preserves the amortized O(1) result; a smaller factor just trades a bigger constant for less wasted memory.

Key idea: the geometric series is the proof - growth by any constant factor gives amortized O(1), while growth by a constant amount gives O(n) per append.

Complexity summary

Operation	Complexity
Index (read or write a[i])	O(1)
Append to end	O(1) amortized
Insert or delete at front or middle	O(n)
Search for a value	O(n)

Space for a dynamic array is O(n): it stores n elements plus a bounded amount of spare capacity. Arrays are the workhorse structure; reach for them whenever you need fast indexed access and mostly append at the end.

Deleting from the end is also amortized O(1) - just decrement the length. Deleting from the front is O(n), because every remaining element shifts down one slot. That asymmetry is worth internalizing: a.pop() is free and a.pop(0) is not, even though they look like siblings. A loop of a.pop(0) calls over n items is a quadratic algorithm hiding in three characters, and it is the single most common accidental O(n^2) in Python code. Use collections.deque when you need to remove from the front.

Key idea: arrays give O(1) indexing and amortized O(1) append and pop-from-end, but O(n) for anything at the front or middle, using O(n) space overall.

When to reach for an array

Choose an array when you index by position, iterate a lot, and mostly grow at the end. That covers a large majority of real collections, and the cache behaviour means arrays often win even where the asymptotics say they should not - deleting from the middle of a 200-element array by shifting is usually faster than the pointer chasing a linked list would need to find the spot in the first place.

Choose something else when your access pattern fights the layout. Frequent insertion or deletion at the front points to a deque; frequent insertion in the middle of a large collection points to a linked list or a balanced tree; lookup by key rather than by position points to a hash table. And if you are storing millions of numbers, consider array.array or NumPy over a plain list: the raw layout removes both the pointer indirection and the per-object overhead, cutting memory by roughly four and a half times.

Key idea: match the structure to the access pattern; arrays win on indexing, iteration, and end-growth, and lose on front and middle edits.

Where people get stuck

• "Appending is always O(1)." Almost always, but the append that triggers a resize is O(n). We say amortized O(1) precisely to acknowledge that. In a latency-sensitive loop, that occasional pause is real - preallocate if it matters.
• "Bigger arrays are slower to index." No. Address arithmetic is one step regardless of size, so indexing is O(1) for any n.
• "Inserting at the front is cheap like appending." Front insertion shifts all n elements, so it is O(n), unlike the amortized O(1) append at the end.
• "A dynamic array wastes no memory." It keeps spare capacity, so it holds some empty slots; this is the small price for fast appends.
• The off-by-one at the boundary. Valid indices run 0 through len(a) - 1, so for i in range(len(a)) is right and range(len(a) + 1) raises IndexError on the last pass. When comparing neighbours with a[i] and a[i+1], the loop must stop at len(a) - 1.
• The aliasing trap in 2D arrays. grid = [[0] * 3] * 3 builds one row and stores the same row object three times, so grid[0][0] = 9 changes all three rows. Write grid = [[0] * 3 for _ in range(3)] instead. The multiplication operator copies references, not contents.
• Mutating while iterating. Removing items from a list inside a for loop over that list silently skips elements, because the loop's internal index keeps advancing while the elements shift down. Build a new list, or iterate over a copy.

Recap

• Arrays store equal-size elements in contiguous memory, so indexing is O(1) by the rule base + i * element_size.
• Contiguity also buys cache locality: one 64-byte line delivers eight 64-bit values, which is why array scans beat pointer chasing at equal Big-O.
• Static arrays have a fixed size; insertion or deletion anywhere but the end shifts elements in O(n).
• Dynamic arrays keep spare capacity and grow by a constant factor when full, giving amortized O(1) append; the proof is the geometric series 1 + 2 + 4 + ... + n/2 = n - 1.
• Growing by a fixed number of slots instead of a factor makes n appends cost O(n^2) in total.
• Overall space is O(n); arrays shine when you need indexed access, iteration, and end-appends, and a.pop(0) in a loop is the classic accidental quadratic.

Sources

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Amortized analysis: The dynamic table. In Introduction to algorithms (4th ed., ch. 16). MIT Press. find source ↗
2. Demaine, E., Ku, J., & Solomon, J. (2020). Lecture 2: Data structures and dynamic arrays. 6.006 Introduction to Algorithms, MIT OpenCourseWare. ocw.mit.edu
3. Morin, P. (2013). Array-based lists. In Open data structures (ch. 2). opendatastructures.org
4. Python Software Foundation. (n.d.). Data structures. The Python tutorial. docs.python.org
5. Python core developers. (n.d.). Objects/listobject.c: list_resize and the over-allocation growth pattern. CPython source. github.com
6. Python Software Foundation. (n.d.). TimeComplexity. Python Wiki. wiki.python.org
7. Sedgewick, R., & Wayne, K. (2011). Bags, queues, and stacks: Resizing arrays. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu

The big picture

The linked list is the structure most often taught and least often used. That is not a criticism of teaching it - the pointer manipulation you learn here is the same manipulation that builds trees, graphs, and hash-table chains. But the honest verdict on the plain linked list as a general-purpose sequence is that modern hardware punishes it, and this lesson will explain exactly why.

The big picture

A linked list is the array's opposite twin. Where an array packs everything into one contiguous block, a linked list scatters items across memory and threads them together with pointers. That single design choice flips the cost of every operation, and understanding the trade-off tells you exactly when each structure is the right tool.

This lesson builds a linked list, compares it operation by operation with arrays, and states the complexity of access, insertion, and deletion.

What a linked list is

A linked list stores elements in separate nodes scattered through memory. A node is a small container holding a value plus a pointer (a reference) to the next node. Picture a scavenger hunt: each clue (node) holds a prize (value) and tells you where to find the next clue, but the clues are hidden all over the house rather than lined up on a shelf. A variable called head points to the first node; the last node points to nothing (in Python, None). Because nodes are linked by pointers rather than laid out contiguously, the list can grow and shrink without ever copying or shifting a block of memory.

Key idea: a linked list is a chain of nodes, each holding a value and a pointer to the next, so it grows without shifting memory.

Building one in Python

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

# Build the list 10 -> 20 -> 30
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)

# Traverse it
node = head
while node is not None:
    print(node.value)
    node = node.next

To read the list you start at head and follow each next pointer until you hit None. There is no way to jump to the middle; you must walk the chain.

Here are the three operations that matter, written so you can run them. Note that each takes O(1) time once you are holding the right node, and that none of them moves any data:

def push_front(head, value):        # O(1)
    node = Node(value)
    node.next = head                # new node points at the old first
    return node                     # the new node IS the new head

def insert_after(node, value):      # O(1) given the node
    new = Node(value)
    new.next = node.next            # ORDER MATTERS: link forward first
    node.next = new                 # then relink the predecessor
    return new

def delete_after(node):             # O(1) given the predecessor
    victim = node.next
    if victim is None:
        return None
    node.next = victim.next         # bypass the victim
    victim.next = None              # optional: help the collector
    return victim.value

The two lines in insert_after must run in that order. Assign node.next = new first and you have overwritten the only reference to the rest of the list, which is now unreachable - a leak in a manual-memory language and silent data loss in Python. Whenever you rewire pointers, attach the new node to what comes after it before you detach anything.

Key idea: linked-list edits are pointer reassignments, not data movement, and the order of those assignments is the difference between working code and a lost list.

Worked example: deleting a node, step by step

Start with the four-node list 10 -> 20 -> 30 -> 40 and delete the value 30. Assume we only have head, so we must first walk to the predecessor:

state 0   head -> [10|*] -> [20|*] -> [30|*] -> [40|/]
          prev = head (10).  Is prev.next.value == 30?  20 != 30, advance.

state 1   prev = node 20.    Is prev.next.value == 30?  YES. Stop.
          Two pointer reads so far; this walk is the O(n) part.

state 2   victim = prev.next          -> node 30
          prev.next = victim.next     -> node 20 now points at node 40
          head -> [10|*] -> [20|*] -----------------> [40|/]
                                        [30|*] is now unreachable

state 3   victim.next = None          -> node 30 fully detached
          final list: 10 -> 20 -> 40

Count the work honestly. Finding the predecessor took 2 pointer hops, and would take up to n - 1 in general, so delete by value on a singly linked list is O(n). The rewiring itself was 2 assignments, O(1). This is the distinction that trips people up: the deletion is constant time, the search for where to delete is not. A linked list is only O(1) for edits when something else - a hash map, an iterator, a previous traversal - has already handed you the node.

Two edge cases will break a naive implementation. Deleting the first node has no predecessor to rewire, so the caller must reassign head; and deleting from an empty list must not dereference None. Both disappear if you use a sentinel node: a permanent dummy node in front of the real head, so every real node has a predecessor and the special case vanishes. Production list code almost always uses one.

Key idea: O(1) deletion assumes you already hold the predecessor; a sentinel node removes the empty-list and first-node special cases that cause most linked-list bugs.

The fundamental trade-off with arrays

Linked lists and arrays are mirror images. To reach the i-th element of a linked list you must follow pointers from the head, one node at a time, so access is O(n), whereas an array gives O(1) indexing. But once you already hold a node, inserting or deleting next to it is just a couple of pointer reassignments, which is O(1), whereas an array must shift elements in O(n). It is the scavenger hunt versus the numbered mailboxes: mailboxes let you jump straight to any number, but adding a mailbox in the middle means renumbering everything after it.

Operation	Array	Linked list
Access i-th element	O(1)	O(n)
Insert or delete at front	O(n)	O(1)
Insert or delete after a known node	O(n)	O(1)
Search for a value	O(n)	O(n)

Key idea: arrays trade cheap indexing for costly middle edits; linked lists make the opposite trade.

The table is correct and, on its own, misleading. It says nothing about the constant factors, and here the constants are enormous. Array elements sit in consecutive bytes, so one 64-byte cache line delivers eight of them and the prefetcher fetches the next line before you need it. Linked-list nodes are separately allocated and can land anywhere, so following each pointer risks a cache miss - roughly a hundred times slower than a hit. Traversing a million-node list can therefore cost a million cache misses, while scanning a million-element array costs about one eighth as many fetches, all of them predicted.

The practical consequence is uncomfortable for the textbook story. For a list of a few thousand items, inserting into the middle of an array - an O(n) memmove of contiguous bytes, which the hardware does extremely fast - frequently beats the O(1) linked-list insert, because the linked list first has to walk the chain to find the spot and pays a miss at every step. Big-O is about growth, not speed; when two structures are both O(n) for the operation you actually perform, the layout decides.

Key idea: Big-O ranks growth, not constants; array contiguity buys a cache advantage large enough to beat a linked list at its own game for small and medium n.

Where linked structures genuinely win

Plain singly linked lists are rarely the right answer for a general sequence. Linked structures are everywhere, though, and the pattern is consistent: they win when you hold references to interior nodes and need to splice them out without touching anything else.

• LRU caches. A hash map from key to node, plus a doubly linked list of nodes in recency order. The map finds any node in O(1), and the list moves it to the front in O(1). Neither structure alone can do both.
• Deques and queues. Python's collections.deque is a doubly linked list of fixed-size blocks - a hybrid that keeps O(1) ends while preserving some cache locality inside each block.
• Hash-table chaining. Each bucket holds a short chain of colliding entries, exactly the structure of Lesson 7.
• Free lists and allocators. The unused memory blocks are themselves the nodes, so the list costs nothing extra to store.

Notice what these share: O(1) splicing of a node you already have, and no need to index by position. Whenever your access pattern is "index into the middle", you wanted an array.

Cycle detection: the tortoise and the hare

A linked list can accidentally point back into itself, and a naive traversal then loops forever. Floyd's algorithm finds a cycle in O(n) time and O(1) space with two pointers moving at different speeds:

def has_cycle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next            # one step
        fast = fast.next.next       # two steps
        if slow is fast:            # identity, not equality
            return True
    return False

Why it works: if there is no cycle, fast reaches the end and the loop exits. If there is a cycle, both pointers eventually enter it, and thereafter the gap between them shrinks by exactly one node per step, because fast gains one position each iteration. A gap that decreases by one every step must reach zero, so they meet within at most L steps for a cycle of length L. Total work is O(n), and the only storage is two pointers.

Trace it on 1 -> 2 -> 3 -> 4 -> back to 2. Positions after each iteration: slow at 2 and fast at 3; slow at 3 and fast at 2 (fast wrapped); slow at 4 and fast at 4 - met, so a cycle exists. Compare is, not ==: two distinct nodes can hold equal values.

Key idea: two pointers at different speeds detect a cycle in O(n) time and O(1) space, because inside a loop the gap between them shrinks by one every step.

Variations and cost

A singly linked list points only forward: each node knows the next but not the previous. A doubly linked list adds a prev pointer in each node so you can walk backward and delete a node in O(1) given only that node. The price is extra memory: linked lists use O(n) space like arrays, but each node also stores one or two pointers, so the constant factor is higher and the nodes are scattered rather than packed. Choose a linked list when you insert and delete at the ends constantly and rarely need random indexed access.

Key idea: a doubly linked list buys backward traversal and easy deletion at the cost of an extra pointer per node.

Where people get stuck

• "Linked lists are always faster than arrays." Only for insertion and deletion at known positions, and even then the cache usually favours the array. For indexed access, arrays win decisively.
• "You can jump to the i-th node quickly." There is no index arithmetic; you must follow i pointers from the head, which is O(n).
• "Linked lists use less memory than arrays." They use more per element: every node stores at least one extra pointer plus its own allocation overhead. A Python node object costs far more than the 8-byte slot a list would use.
• "Insertion is O(1), full stop." Insertion at a node you already hold is O(1). Insertion at position i, or before a given value, is O(n) because of the search.
• Losing the head. head = head.next in a traversal loop destroys your only handle on the list. Walk with a separate cursor variable and leave head alone.
• Forgetting the empty and single-node cases. Almost every linked-list bug lives at head is None or at the last node, where node.next is None and node.next.next raises AttributeError. Test both before you test anything else.
• Stale tail pointers. If you keep a tail reference for O(1) appends, every delete that removes the last node must update it. A tail pointing at a detached node produces a list that silently loses appends.

Recap

• A linked list chains nodes by pointers; head points to the first, and the last points to None.
• Access is O(n) because you must follow pointers, but insertion or deletion at a node you already hold is O(1) - two assignments, in the order "link forward, then relink back".
• Arrays and linked lists are mirror images in Big-O, but cache locality tilts the practical comparison strongly toward arrays.
• Doubly linked lists add a prev pointer for backward traversal and O(1) deletion given only the node, at the cost of extra memory.
• A sentinel node removes the empty-list and first-node special cases that cause most linked-list bugs.
• Floyd's tortoise and hare detects a cycle in O(n) time and O(1) space; the gap between the pointers shrinks by one per step inside the loop.

Learn the pointer surgery here and the rest of the course gets easier: a binary tree is a node with two next pointers, and a graph is a node with as many as it likes.

Sources

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Elementary data structures: Linked lists. In Introduction to algorithms (4th ed., ch. 10). MIT Press. find source ↗
2. Morin, P. (2013). Linked lists. In Open data structures (ch. 3). opendatastructures.org
3. Sedgewick, R., & Wayne, K. (2011). Bags, queues, and stacks: Linked lists. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
4. Halim, S., Halim, F., & Koh, Z. C. (n.d.). Linked list (single, doubly), stack, queue, deque. VisuAlgo, National University of Singapore. visualgo.net
5. Python Software Foundation. (n.d.). collections: deque objects. Python 3 documentation. docs.python.org
6. Malan, D. J. (2025). Lecture 5: Data structures. CS50x, Harvard University. cs50.harvard.edu
7. Galles, D. (n.d.). Data structure visualization. University of San Francisco. cs.usfca.edu

The big picture

Most data structures are defined by what they let you do. Stacks and queues are defined by what they refuse. You cannot reach into the middle, you cannot index, you cannot reorder - and those refusals are the point, because a structure that only permits one kind of access is a structure whose behaviour you can reason about completely.

The big picture

Stacks and queues are the two most important restricted data structures: they deliberately limit where you can add and remove items, and that limitation is exactly what makes them useful. By fixing the order in which items leave, they model real processes like undo history and waiting lines, and they power core algorithms later in this course.

This lesson defines the two ordering disciplines, implements each with the right Python tool, and states their costs.

Both are abstract data types (ADTs): a specification of operations and their behaviour, separate from any implementation. "Stack" means push, pop, peek, and is-empty, with LIFO ordering. It does not mean array, and it does not mean linked list - you can build a conforming stack from either, and code written against the interface will not notice which you chose. Keeping the interface and the implementation apart is what lets you swap a list for a deque later without rewriting the algorithm on top.

Key idea: an ADT is a contract about operations and ordering; the data structure is one way of honouring that contract, and the two should be chosen separately.

Stack: last in, first out

A stack follows LIFO order, which stands for last in, first out. The picture is a stack of plates: you add a plate to the top and take one off the top, and the last plate you set down is the first one you pick up. You push onto the top and pop off the top; you never reach into the middle. A Python list makes a perfect stack because appending and popping at the end are both O(1).

stack = []
stack.append("a")   # push
stack.append("b")   # push
top = stack.pop()   # pop -> "b" (LIFO)
print(top, stack)   # b ['a']

Stacks appear everywhere: the function call stack that tracks pending calls, the undo button in an editor, matching brackets in code, and depth-first search later in this course. Both push and pop are O(1).

The call stack is worth dwelling on, because it is not a metaphor - it is a literal stack. Each call pushes a frame holding the arguments, the local variables, and the address to return to; each return pops one. That is why the most recently called function is always the first to finish, why a traceback prints innermost-first, and why unbounded recursion produces a stack overflow. Everything you learned about recursion depth in Lesson 3 is a statement about how tall this stack grows.

Key idea: a stack is LIFO like a stack of plates; push and pop act only on the top and are both O(1) - and the call stack that runs your program is exactly this structure.

Worked example: checking balanced brackets

The classic stack problem. Scan the string; push every opening bracket; on a closing bracket, pop and check that it matches. Balanced means every pop matched and the stack is empty at the end.

def is_balanced(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False        # wrong closer, or nothing to close
    return len(stack) == 0          # leftovers mean unclosed openers

Trace it on "([]{})", showing the stack after each character:

char   action                       stack after
 (     push                         ['(']
 [     push                         ['(', '[']
 ]     pop '[' , matches '['        ['(']
 {     push                         ['(', '{']
 }     pop '{' , matches '{'        ['(']
 )     pop '(' , matches '('        []
 end   stack empty                  BALANCED

Now the interesting failure, "([)]", which a naive counter of brackets would wrongly accept because it has two openers and two closers:

char   action                       stack after
 (     push                         ['(']
 [     push                         ['(', '[']
 )     pop gives '[' , expected '(' MISMATCH -> return False

Counting cannot catch that; the stack can, because LIFO order encodes nesting. Two more edge cases the code handles deliberately: ")(" fails on the first character, where the stack is empty and there is nothing to pop, and "((" fails at the end, where the stack is non-empty. Each character is pushed at most once and popped at most once, so the whole scan is O(n) time, and the stack holds at most n items, so O(n) space - reached by a string of n opening brackets.

Key idea: whenever a problem involves nesting or "most recent unmatched thing", a stack is almost certainly the structure, and the cost is one push and one pop per item.

Queue: first in, first out

A queue follows FIFO order, first in, first out, exactly like a line at a store: the first person to arrive is the first served. You enqueue at the back and dequeue from the front. A plain Python list is a poor queue, because popping from the front with list.pop(0) forces every remaining element to shift left, an O(n) operation. Instead use collections.deque, a double-ended queue that adds and removes at both ends in O(1).

from collections import deque
q = deque()
q.append("a")        # enqueue at back
q.append("b")
first = q.popleft()  # dequeue from front -> "a" (FIFO)
print(first, q)      # a deque(['b'])

Queues model anything served in arrival order: print jobs, task scheduling, and breadth-first search later on. With a deque, enqueue and dequeue are both O(1).

Quantify the mistake, because "O(n) instead of O(1)" understates it. Draining n items with list.pop(0) shifts n - 1 elements on the first pop, n - 2 on the second, and so on: the total is n(n-1)/2 element moves, which is Theta(n^2). Draining a 100,000-item list that way costs about five billion moves; with a deque it costs 100,000 pops. This is the same triangular sum from Lesson 2, and it is why "use a deque" is not a style preference.

Key idea: a queue is FIFO like a checkout line; use a deque so both enqueue and dequeue stay O(1), because n front-pops from a list cost n(n-1)/2 shifts.

Building a queue on a fixed array: the ring buffer

Python hands you a deque, but it is worth seeing how a queue is built on an array, because that is what runs inside network stacks and audio drivers. The trick is a circular buffer: keep a fixed array plus a head index and a count, and let the indices wrap around with modular arithmetic.

class RingQueue:
    def __init__(self, capacity):
        self.buf = [None] * capacity
        self.head = 0          # index of the front item
        self.size = 0          # how many items are stored

    def enqueue(self, x):                      # O(1)
        if self.size == len(self.buf):
            raise OverflowError("queue is full")
        self.buf[(self.head + self.size) % len(self.buf)] = x
        self.size += 1

    def dequeue(self):                         # O(1)
        if self.size == 0:
            raise IndexError("queue is empty")
        x = self.buf[self.head]
        self.buf[self.head] = None
        self.head = (self.head + 1) % len(self.buf)
        self.size -= 1
        return x

Trace a capacity-4 buffer through enqueue A, B, C, then two dequeues, then enqueue D, E:

operation      buf                head  size
start          [_, _, _, _]        0     0
enq A          [A, _, _, _]        0     1
enq B          [A, B, _, _]        0     2
enq C          [A, B, C, _]        0     3
deq -> A       [_, B, C, _]        1     2
deq -> B       [_, _, C, _]        2     1
enq D          [_, _, C, D]        2     2
enq E          [E, _, C, D]        2     3   <- wrapped around to slot 0

Slot 0 was reused without moving anything, which is the entire point: no shifting, ever, so both operations are genuinely O(1) with a tiny constant. Note the design decision to store an explicit size. The tempting alternative - two indices, head and tail - runs into an ambiguity, because head == tail means both "empty" and "completely full". Implementations resolve it by keeping a count, by keeping one slot permanently unused, or by tracking total enqueues and dequeues as monotonically increasing numbers. Choosing none of the three is a classic bug that appears only when the buffer fills exactly.

Key idea: modular arithmetic turns a fixed array into a queue with O(1) ends and no shifting; store an explicit count so that "full" and "empty" are distinguishable.

Summary

Structure	Order	Add	Remove
Stack	LIFO	push O(1)	pop O(1)
Queue (deque)	FIFO	enqueue O(1)	dequeue O(1)

Both use O(n) space to hold n items. The design lesson: pick the discipline that matches your problem, LIFO for "handle the most recent first," FIFO for "handle the oldest first."

That choice has visible consequences in Lesson 16. Breadth-first search and depth-first search are the same traversal algorithm; the only difference is whether the frontier of discovered-but-unvisited nodes is held in a queue or a stack. Swap the container and BFS becomes DFS. Few facts in this course show so cleanly that a data structure is a decision about behaviour, not just about storage.

Key idea: choose a stack when recency matters and a queue when arrival order matters; both cost O(n) space, and swapping one for the other turns BFS into DFS.

Where people get stuck

• "A Python list is a fine queue." It is a fine stack but a poor queue, because front removal shifts all elements in O(n), making a full drain quadratic. Use collections.deque.
• "Stacks and queues let you access any element." No. They restrict you to one end (or two specified ends); reaching into the middle is not part of the interface. If you find yourself indexing into a stack, you wanted a list.
• "FIFO and LIFO are the same if the data is sorted." The discipline is about the order of operations, not the values, so sorting is irrelevant. A structure that orders by value is a heap, and that is Lesson 14.
• "A deque is slower than a list." For end operations they are both O(1), and a deque is far faster at the front. A list is slightly faster to index, which a queue never does.
• Popping an empty stack. [].pop() raises IndexError. Every pop needs a guard, and forgetting it in the bracket-matching problem is the standard bug: the closing bracket with nothing to close.
• Confusing peek with pop. Peek reads the top and leaves it; pop removes it. In Python, peek is stack[-1], and writing stack.pop() when you meant to peek quietly consumes the item you were about to inspect.
• Reaching for queue.Queue by default. That class is a thread-safe queue with locking, for producer-consumer work across threads. Inside a single-threaded algorithm it just adds synchronization overhead; use a deque.

Recap

• Stack and queue are abstract data types: an interface plus an ordering rule, independent of the structure that implements them.
• A stack is LIFO: push and pop at the top, both O(1). The call stack that runs your program is a literal instance of it.
• A queue is FIFO: enqueue at the back, dequeue at the front; use a deque for O(1) at both ends.
• A plain list makes a good stack but a poor queue, because n front-pops cost n(n-1)/2 element shifts.
• Bracket matching is the canonical stack problem: O(n) time, O(n) space, and it catches the interleaving "([)]" that simple counting cannot.
• A ring buffer implements a queue on a fixed array using modular arithmetic; keep an explicit count so full and empty are distinguishable.

Whenever a problem says "most recent" reach for a stack, and whenever it says "in order of arrival" reach for a queue. Half of graph algorithms are that sentence applied carefully.

Sources

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Elementary data structures: Stacks and queues. In Introduction to algorithms (4th ed., ch. 10). MIT Press. find source ↗
2. Sedgewick, R., & Wayne, K. (2011). Bags, queues, and stacks. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
3. Python Software Foundation. (n.d.). collections: deque objects. Python 3 documentation. docs.python.org
4. Python Software Foundation. (n.d.). Data structures: Using lists as stacks and as queues. The Python tutorial. docs.python.org
5. Morin, P. (2013). Array-based lists: ArrayStack, ArrayQueue, and ArrayDeque. In Open data structures (ch. 2). opendatastructures.org
6. Halim, S., Halim, F., & Koh, Z. C. (n.d.). Linked list (single, doubly), stack, queue, deque. VisuAlgo, National University of Singapore. visualgo.net
7. Python Software Foundation. (n.d.). queue - A synchronized queue class. Python 3 documentation. docs.python.org

The big picture

Every other structure in this course pays something for a lookup: an array pays O(n) to search, a tree pays O(log n) to descend. The hash table pays O(1), independent of how much data it holds - a claim that sounds impossible until you see the trick, and comes with fine print that this lesson insists on reading aloud.

The big picture

The hash table is arguably the most useful data structure in everyday programming. It finds a key almost instantly, no matter how large the collection, which is why it underpins Python's dict and set and shows up in caches, databases, and compilers. Understanding how it achieves that speed, and when it does not, lets you use it with confidence.

This lesson explains the hash function, the collision problem and its fix, and the honest best and worst case costs.

What a hash table is

A hash table stores key-value pairs and finds a key in O(1) average time, far faster than scanning a list. The magic is a hash function: it takes a key and computes an integer, which is then reduced (with the modulo operator) to an index into an underlying array of buckets, where a bucket is one slot of that array.

The analogy is a coat check at a theater: you hand over your coat and get a numbered tag; the number sends the coat straight to a specific hook, and to retrieve it the attendant goes right to that hook rather than searching every coat. To store or find a key you hash it, jump straight to that bucket, and look there. No scanning required.

A hash function has to satisfy four requirements, and they pull against each other:

• Deterministic. The same key must always hash to the same value, or you can never find what you stored. This is why a mutable object cannot safely be a key.
• Uniform. Keys should spread evenly over the buckets. Clumping is what turns O(1) into O(n).
• Fast. The hash is computed on every single operation, so an expensive hash cancels the benefit it provides.
• Avalanching. A one-character change in the key should scramble the whole output. Without this, similar keys land in nearby buckets and cluster.

In Python the requirement pair is __hash__ and __eq__: objects that compare equal must hash equal, otherwise the table can store two "equal" keys and find neither reliably. That is the entire contract, and it is why lists are unhashable while tuples are not.

prices = {}                 # a dict is a hash table
prices["apple"] = 30        # hash "apple" -> a bucket, store there
prices["banana"] = 10
print(prices["apple"])      # hash again -> same bucket -> 30, O(1) average
print("banana" in prices)   # membership test, O(1) average

Key idea: a hash function turns a key into a bucket index like a coat-check tag, so lookup jumps straight to the value in O(1) on average.

Collisions

Different keys can hash to the same bucket. This is a collision, and it is unavoidable because there are more possible keys than buckets (two coats can be assigned the same hook). A common fix is separate chaining: each bucket holds a small linked list of all pairs that landed there. To find a key you hash to its bucket, then walk that short list checking keys. If the hash function spreads keys evenly and the table is not too full, each list stays tiny, so lookups stay effectively O(1) on average.

Key idea: collisions are inevitable, and separate chaining resolves them by keeping a short list per bucket.

Worked example: a deliberate collision

Build a tiny table with 8 buckets and a deliberately weak hash - the sum of the character codes, modulo 8. Weak hashes make collisions easy to arrange, which is exactly what we want for a trace:

h(key) = (sum of ord(c) for c in key) % 8

"cat" -> 99 + 97 + 116 = 312 -> 312 % 8 = 0
"dog" -> 100 + 111 + 103 = 314 -> 2
"fig" -> 102 + 105 + 103 = 310 -> 6
"act" -> 97 + 99 + 116 = 312 -> 0     <- SAME BUCKET AS "cat"
"emu" -> 101 + 109 + 117 = 327 -> 7

"act" is an anagram of "cat", and a sum-based hash cannot tell anagrams apart - a concrete illustration of why real hash functions mix position into the result. Insert all five with separate chaining and the table looks like this:

bucket 0: [cat] -> [act]        <- a chain of length 2
bucket 1: empty
bucket 2: [dog]
bucket 3: empty
bucket 4: empty
bucket 5: empty
bucket 6: [fig]
bucket 7: [emu]

Looking up "act" costs one hash, one jump to bucket 0, then a walk of the chain comparing keys: "cat" is not equal, "act" is - two comparisons. Looking up "ant" (which hashes to 3) costs one hash and finds an empty bucket, so it reports "absent" in zero comparisons.

Now redo it with open addressing, where every entry lives directly in the array and a collision means probing the next slot (linear probing):

insert cat   h=0, slot 0 free           -> [cat][ _ ][ _ ][ _ ][ _ ][ _ ][ _ ][ _ ]
insert dog   h=2, slot 2 free           -> [cat][ _ ][dog][ _ ][ _ ][ _ ][ _ ][ _ ]
insert fig   h=6, slot 6 free           -> [cat][ _ ][dog][ _ ][ _ ][ _ ][fig][ _ ]
insert act   h=0, slot 0 taken by cat,
             probe slot 1, free         -> [cat][act][dog][ _ ][ _ ][ _ ][fig][ _ ]
insert emu   h=7, slot 7 free           -> [cat][act][dog][ _ ][ _ ][ _ ][fig][emu]

lookup act   h=0 -> slot 0 is cat (no) -> slot 1 is act (yes).  2 probes.
lookup ant   h=3 -> slot 3 is EMPTY -> absent.  1 probe.

Here is the bug that open addressing creates, and it is a famous one. Delete "cat" by simply blanking slot 0. Now look up "act": we hash to 0, find slot 0 empty, and conclude the key is absent - but "act" is sitting in slot 1. Blanking a slot breaks the probe chain that other keys depend on. The fix is a tombstone: mark the slot as "deleted but keep probing" rather than "empty, stop". Tombstones accumulate and eventually force a rehash, which is one reason chaining is easier to get right.

Key idea: chaining puts collisions in a list per bucket; open addressing puts them in the next free slot, which is faster and more cache-friendly but requires tombstones on deletion.

Load factor and resizing

The load factor is the number of stored items divided by the number of buckets. As it rises, chains get longer and lookups slow down. So hash tables resize: when the load factor crosses a threshold (often around 0.7), they allocate a larger bucket array and rehash every key into it. Like the doubling trick for dynamic arrays, this spreads the occasional expensive rebuild over many operations, making insertion amortized O(1).

The load factor is not a vague guideline; it produces the actual expected cost. Call it alpha. With chaining and a hash that spreads keys uniformly, the expected chain length is exactly alpha, so an unsuccessful search costs about 1 + alpha comparisons and a successful one about 1 + alpha/2. Both are constants that do not mention n - that is where "O(1)" comes from. It is a statement about the load factor, not about magic.

Open addressing degrades far more sharply, because probes collide with each other as well as with the target. For linear probing the classical estimates are:

                        alpha = 0.5    alpha = 0.75   alpha = 0.9
successful search        1.5 probes     2.5 probes     5.5 probes
unsuccessful search      2.5 probes     8.5 probes    50.5 probes

unsuccessful ~ (1/2) * (1 + 1 / (1 - alpha)^2)
successful   ~ (1/2) * (1 + 1 / (1 - alpha))

At 90 percent full an unsuccessful lookup costs about fifty probes instead of two. The curve is nearly flat until roughly two-thirds full and then goes vertical, which is precisely why implementations resize well before the table is truly out of room. CPython's dict grows once the used entries exceed two-thirds of the table.

Key idea: keeping the load factor low by resizing keeps chains short, preserving near-O(1) operations - expected cost is about 1 + alpha for chaining, and it explodes past alpha = 0.7 for open addressing.

Honest complexity

Operation	Average	Worst case
Insert	O(1)	O(n)
Lookup	O(1)	O(n)
Delete	O(1)	O(n)

The worst case is O(n), which happens if a bad hash function dumps every key into one bucket, degrading the table to a single long list you must scan. In practice, good hash functions make that vanishingly rare, so hash tables are the default choice for fast lookup, deduplication, and counting. Space is O(n): the buckets plus the stored entries.

The worst case is not purely theoretical. If an attacker can choose your keys - form fields, JSON payloads, HTTP headers - they can deliberately generate colliding keys and turn every request into an O(n) scan, an algorithmic denial-of-service. Python's defence is hash randomization: since version 3.3 the hash of a string is salted with a per-process random seed, so an attacker cannot predict which keys collide. That is also why hash("abc") differs between runs unless you pin PYTHONHASHSEED, and why hash values must never be persisted to disk.

Key idea: hash tables are O(1) on average but O(n) in the pathological worst case, so they are fast in practice yet not a hard guarantee - and the worst case can be induced deliberately, which is what hash randomization defends against.

When a tree beats a hash map

Hash tables win on raw lookup, so the interesting question is what makes a balanced tree (Lesson 12) the better choice. Four situations:

• You need order. A tree can iterate keys in sorted order for free; a hash table must collect and sort them, which costs O(n log n).
• You need range queries. "All keys between 100 and 200" is a natural tree walk and impossible for a hash table without scanning everything, because hashing deliberately destroys the relationship between nearby keys.
• You need a worst-case guarantee. A balanced tree is O(log n) always. In a real-time or adversarial setting, a guaranteed log n beats an average-case constant.
• The keys have no good hash. If a key is expensive to hash or only supports comparison, a tree needs nothing more than an ordering.

Otherwise, reach for the hash table. For plain "store and retrieve by key", it is faster in both theory and practice, and it is the right default.

Key idea: hash tables trade order for speed; use a tree when you need sorted iteration, range queries, or a hard worst-case bound.

Where people get stuck

• "Hash table lookup is guaranteed O(1)." It is O(1) on average, under a uniformity assumption about the hash. With adversarial or badly chosen keys, all entries can collide and lookup becomes O(n).
• "Collisions mean the table is broken." Collisions are normal and expected; by the birthday paradox, 23 random keys in a 365-bucket table already collide about half the time. Chaining and probing handle them gracefully.
• "Hash tables keep keys in sorted order." They do not. Python's dict preserves insertion order as of 3.7, which is not sorted order and is a property of that implementation, not of hash tables.
• "A fuller table is always fine." A high load factor lengthens chains and multiplies probes, which is exactly why tables resize at around two-thirds full.
• Mutating a key after insertion. If a key's hash changes while it sits in the table, the entry becomes unreachable: you look in the new bucket and it is in the old one. This is why keys must be immutable, and why d[[1,2]] = x raises TypeError.
• Defining __eq__ without __hash__. Python then makes your class unhashable, which is the safe default. Define both together or neither, and make sure equal objects hash equal.
• Deleting by blanking a slot in open addressing. It breaks every probe chain passing through that slot. Use tombstones.

Recap

• A hash function maps a key to a bucket index, giving O(1) average lookup; it must be deterministic, uniform, fast, and avalanching.
• Collisions are unavoidable and resolved by separate chaining (a list per bucket) or open addressing (probe to the next free slot).
• The load factor alpha sets the real cost: about 1 + alpha comparisons for chaining, rising steeply past 0.7 for linear probing.
• Resizing and rehashing keep the load factor low, making insertion amortized O(1); CPython grows a dict past two-thirds occupancy.
• Deleting under open addressing needs tombstones, or later lookups will stop at the gap and report keys as missing.
• Average operations are O(1) and the worst case is O(n); use a balanced tree instead when you need sorted order, range queries, or a hard guarantee.

The hash table is the default answer to "find this by key". Know the assumption it rests on - a good hash and a bounded load factor - and you will know the few cases where it is the wrong answer.

Sources

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Hash tables. In Introduction to algorithms (4th ed., ch. 11). MIT Press. find source ↗
2. Demaine, E., Ku, J., & Solomon, J. (2020). Lecture 4: Hashing. 6.006 Introduction to Algorithms, MIT OpenCourseWare. ocw.mit.edu
3. Morin, P. (2013). Hash tables. In Open data structures (ch. 5). opendatastructures.org
4. Sedgewick, R., & Wayne, K. (2011). Hash tables. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
5. Python Software Foundation. (n.d.). Built-in types: Mapping types - dict. Python 3 documentation. docs.python.org
6. Python core developers. (n.d.). Objects/dictobject.c: Probing, USABLE_FRACTION, and the compact dict layout. CPython source. github.com
7. Halim, S., Halim, F., & Koh, Z. C. (n.d.). Hash table: Separate chaining and open addressing. VisuAlgo, National University of Singapore. visualgo.net

The big picture

The hardest part of recursion is a leap of faith. You write a function that calls itself, and to believe it works you must trust the recursive call to return the right answer - the very function you have not finished writing. That trust feels illegitimate the first time and becomes second nature the tenth, and this lesson is about making the transition on purpose rather than by accident.

The big picture

Recursion is a way of thinking as much as a coding technique: solve a big problem by assuming you can already solve a slightly smaller version of it, then handle just the last step. It feels circular at first, but with a clear stopping condition it is both correct and often the clearest possible solution, especially for the divide-and-conquer sorts coming next.

This lesson defines the two parts every recursion needs, traces one carefully, and analyzes its time and space cost.

The leap of faith is not really faith; it is mathematical induction wearing a different hat. A proof by induction shows a statement holds for a base value and that truth at n - 1 implies truth at n. A recursive function does exactly this: the base case is the base of the induction, and the recursive case is the inductive step, assuming a correct answer for the smaller input and building the answer for n from it. If you can write the induction, the code is correct - and if you cannot, no amount of tracing will save it.

Key idea: a recursive function is an inductive proof that runs; base case plus inductive step is exactly base case plus recursive case.

What recursion is

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem. Every correct recursion has two parts: a base case that returns an answer directly without recursing, and a recursive case that reduces the problem and calls itself. The base case is the floor of the staircase: without it, the function keeps stepping down forever and eventually crashes with a stack overflow.

Key idea: every recursion needs a base case that stops and a recursive case that shrinks the problem toward that base case.

Factorial: the classic

def factorial(n):
    if n == 0:                 # base case
        return 1
    return n * factorial(n - 1)  # recursive case

print(factorial(5))            # 120

To evaluate factorial(5), Python suspends it to compute factorial(4), which suspends to compute factorial(3), and so on down to factorial(0), which returns 1 directly. Then the answers multiply back up the chain: 1, then 1 times 1, then 2 times 1, then 3 times 2, giving 1, 1, 2, 6, 24, 120. There are n plus 1 calls, each doing O(1) work, so factorial is O(n) time. The n stacked calls alive at once make it O(n) space.

Key idea: a chain of n recursive calls, each doing constant work, is O(n) time and O(n) stack space.

Worked example: watching the stack grow and unwind

Trace factorial(4) and write out the call stack at every moment. The left column is the stack, deepest frame last:

step  event                          call stack (top on the right)
 1    call factorial(4)              [f(4)]
 2    4 != 0, needs factorial(3)     [f(4), f(3)]
 3    3 != 0, needs factorial(2)     [f(4), f(3), f(2)]
 4    2 != 0, needs factorial(1)     [f(4), f(3), f(2), f(1)]
 5    1 != 0, needs factorial(0)     [f(4), f(3), f(2), f(1), f(0)]
 6    BASE CASE: f(0) returns 1      [f(4), f(3), f(2), f(1)]
 7    f(1) = 1 * 1 = 1, returns      [f(4), f(3), f(2)]
 8    f(2) = 2 * 1 = 2, returns      [f(4), f(3)]
 9    f(3) = 3 * 2 = 6, returns      [f(4)]
10    f(4) = 4 * 6 = 24, returns     []          answer 24

Three things are visible in that trace and in no other way. First, nothing multiplies on the way down - the descent only records pending work, and every multiplication happens during the unwind. Second, the stack reaches its maximum depth of 5 frames at step 5, which is where the O(n) space comes from. Third, the base case runs exactly once, and it is the only step that returns a value without asking a question.

Now remove the base case and re-read the trace. Steps 1 through 5 keep going: f(-1), f(-2), f(-3), forever, each adding a frame. CPython stops it at 1000 frames with a RecursionError, which is a guard rail and not a solution. The other failure mode is subtler: a base case that exists but is never reached. A function that recurses on n - 2 with a base case at n == 0 works for even n and runs off to negative infinity for odd n. Check that every path shrinks the input and that the shrinking sequence actually lands on a base case.

Key idea: the descent stacks up pending work and the unwind computes it; a base case must be not only present but reachable from every input.

Recurrences: turning a recursion into a Big-O

To analyze a recursion, write down what it costs in terms of itself. That equation is a recurrence relation, and four patterns cover nearly everything in this course:

RECURRENCE               MEANING                        SOLUTION   EXAMPLE
T(n) = T(n-1) + O(1)     one call, shrink by 1          O(n)       factorial
T(n) = T(n/2) + O(1)     one call, halve the input      O(log n)   binary search
T(n) = 2T(n/2) + O(n)    two halves plus a linear pass  O(n log n) merge sort
T(n) = 2T(n-1) + O(1)    two calls, shrink by 1         O(2^n)     naive Fibonacci

Notice the difference between the second and third rows: one recursive call on half the data gives a logarithm, while two calls on halves gives n log n. And compare rows three and four - halving versus decrementing is the entire distance between "fast" and "impossible".

The recursion-tree argument makes the third row concrete. Level 0 has one problem of size n costing n. Level 1 has two problems of size n/2, each costing n/2, so n again. Level 2 has four of size n/4, again n. Every level costs n, and the levels run out after log2(n) halvings, so the total is n * log2(n). Draw two or three levels of the tree and the answer usually falls out.

The master theorem mechanizes this for recurrences of the form T(n) = a*T(n/b) + f(n): compare f(n) against n raised to log base b of a. When they match, as they do for merge sort with a = 2, b = 2, and f(n) = n, the answer picks up a log n factor. You do not need to memorize its three cases; you do need to recognize that "how many subproblems, how much smaller, how much work to combine" determines the answer.

Key idea: write the recurrence first, then solve it; halving the input gives logarithms, and branching into two full-size-minus-one calls gives exponentials.

Recursion and the call stack

Each active call keeps a frame on the call stack until it returns, like a pile of paused tasks waiting to finish. The maximum number of frames alive at once is the recursion depth, and it sets the space complexity. This is why deeply recursive code can exhaust memory even when it builds no arrays or lists: the frames themselves take space.

Key idea: recursion depth equals the number of paused calls on the stack, and that depth is the space cost.

When recursion shines

Recursion is the natural fit for self-similar problems, ones whose solution is built from solutions to smaller copies of themselves: walking a folder tree whose subfolders are themselves trees, exploring a maze, or the divide-and-conquer sorts in the next module. A closely related idea is divide and conquer: split the problem into smaller independent parts, solve each recursively, and combine the results. Anything recursive can be rewritten with a loop and an explicit stack, but for self-similar problems the recursive version is usually far clearer. Always write the base case first, and make sure every recursive call moves toward it.

def count_down(n):
    if n == 0:            # base case
        print("done")
        return
    print(n)
    count_down(n - 1)     # moves toward the base case

count_down(3)            # 3, 2, 1, done

Key idea: reach for recursion when a problem is self-similar; write the base case first and shrink toward it every call.

When to convert recursion into a loop

count_down above is tail recursive: the recursive call is the last thing it does, with no pending work to return to. Some languages detect this and reuse the stack frame, turning the recursion into a loop for free. Python deliberately does not - Guido van Rossum has argued that eliminating frames would destroy the tracebacks that make debugging possible. So in Python a tail-recursive function still costs O(n) stack, and converting it by hand is a real optimization:

def count_down_iter(n):        # same behaviour, O(1) stack
    while n > 0:
        print(n)
        n = n - 1
    print("done")

The rule of thumb: convert to a loop when the recursion depth is proportional to n and n can be large. Leave it recursive when the depth is proportional to log n - a tree of a billion nodes is only about 30 frames deep - or when the structure is genuinely branching, because a hand-rolled explicit stack is just the call stack with more opportunities for bugs.

The other transformation worth knowing is caching. Any pure recursive function whose subproblems repeat can be memoized with one line:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n-1) + fib(n-2)   # now O(n), not O(1.618^n)

The decorator stores results by argument, so each distinct n is computed once. It only works when the function is deterministic and its arguments are hashable, which is the same contract as any hash-table key.

Key idea: Python does not optimize tail calls, so convert linear-depth recursions to loops; keep recursion for logarithmic depth and branching structures, and reach for lru_cache when subproblems repeat.

Where people get stuck

• "Recursion is always slower than a loop." It has some call overhead, but for the same algorithm the growth class is identical; clarity often outweighs the small constant cost.
• "Recursion uses no extra memory." Each pending call holds a stack frame, so depth-n recursion uses O(n) stack space even with no data structures.
• "You can skip the base case if the input is small." Without a reachable base case the recursion never stops and overflows the stack. Present is not the same as reachable.
• "More recursion means a better solution." Recursion helps only when the problem is genuinely self-similar; otherwise a simple loop is clearer and leaner.
• Slicing inside the recursion. solve(a[1:]) copies the rest of the list at every level, silently adding O(n) time and O(n) space per call and turning a linear algorithm into a quadratic one. Pass a start index instead.
• Mutable default arguments. def walk(node, seen=[]) creates that list once, at function definition, and every later call shares it. Use seen=None and build a fresh list inside.
• Tracing instead of trusting. Following five levels of calls in your head is how people convince themselves recursion is hard. Check the base case, check that the input shrinks, and assume the recursive call returns the right answer. That is the whole method.

Recap

• Recursion solves a problem by calling itself on a smaller instance, needing a base case and a recursive case - the two halves of an inductive proof.
• The descent stacks pending work and the unwind computes it; factorial(n) makes n + 1 calls, so it is O(n) time and O(n) stack space.
• Recursion depth is the count of paused calls and sets the space cost; CPython stops you at 1000 frames.
• Write the recurrence to get the Big-O: T(n-1) + O(1) gives O(n), T(n/2) + O(1) gives O(log n), 2T(n/2) + O(n) gives O(n log n), and 2T(n-1) + O(1) gives O(2^n).
• The recursion tree for merge sort has log2(n) levels each costing n, which is where n log n comes from.
• Python does not eliminate tail calls, so convert linear-depth recursions to loops; memoize with lru_cache when subproblems repeat.

Every sort, tree, and graph algorithm in the rest of this course is recursive at heart. Get comfortable writing the base case first and the recurrence second, and the remaining lessons will feel like variations you have already seen.

Sources

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Divide-and-conquer: Recurrences and the master method. In Introduction to algorithms (4th ed., ch. 4). MIT Press. find source ↗
2. Demaine, E., Ku, J., & Solomon, J. (2020). Lecture notes: Recursion and recurrences. 6.006 Introduction to Algorithms, MIT OpenCourseWare. ocw.mit.edu
3. Python Software Foundation. (n.d.). sys: getrecursionlimit and setrecursionlimit. Python 3 documentation. docs.python.org
4. Python Software Foundation. (n.d.). functools: lru_cache. Python 3 documentation. docs.python.org
5. Halim, S., Halim, F., & Koh, Z. C. (n.d.). Recursion tree and DAG. VisuAlgo, National University of Singapore. visualgo.net
6. Malan, D. J. (2025). Lecture 3: Algorithms: Recursion. CS50x, Harvard University. cs50.harvard.edu
7. Demaine, E., & Devadas, S. (2015). Lecture notes: Divide and conquer. 6.046J Design and Analysis of Algorithms, MIT OpenCourseWare. ocw.mit.edu

The big picture

Insertion sort is the algorithm every card player already knows and nobody was taught. Pick up a hand one card at a time, slide each new card left until it sits in the right place, and you have executed it exactly. This lesson turns that intuition into code, then counts the work precisely enough to say when the "slow" sort is actually the fast choice.

The big picture

Sorting, putting items into order, is one of the most studied problems in computing, and it is the perfect stage for seeing complexity in action. We begin with two simple sorts that anyone can follow by hand. They are slow on large inputs, but they teach the mechanics and, in the case of insertion sort, are genuinely useful on small or nearly sorted data.

This lesson traces bubble sort and insertion sort, explains why both are O(n squared) in the worst case, and shows when insertion sort is the right pick.

Comparison sorts

Both sorts here are comparison sorts: they order items purely by comparing pairs and swapping when a pair is out of order. That is the only tool they use. Both run in O(n^2) time in the worst case, which makes them slow on large inputs but easy to reason about.

Key idea: a comparison sort orders data by comparing pairs; the two here are O(n squared) in the worst case.

Bubble sort

Bubble sort repeatedly walks the list, comparing each adjacent pair and swapping them if they are out of order (a swap just exchanges two elements' positions). Each full pass "bubbles" the largest remaining element to the end, the way the biggest bubble rises to the top of a glass. After at most n minus 1 passes the list is sorted.

def bubble_sort(a):
    n = len(a)
    for i in range(n):
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]  # swap
    return a

Trace one pass on [3, 1, 2]: compare 3 and 1, swap to get [1, 3, 2]; compare 3 and 2, swap to get [1, 2, 3].

The largest, 3, has bubbled to the end. Two nested loops over n elements give O(n^2) comparisons in the worst and average case. It sorts in place, so space is O(1). Bubble sort is rarely used in practice; its value is teaching how sorting works.

Count it exactly rather than waving at "two nested loops". The inner loop runs n - 1 times on pass 0, n - 2 times on pass 1, and so on down to 1, because each pass parks one more element permanently at the end:

comparisons = (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2

n = 10   ->  45 comparisons
n = 100  ->  4,950
n = 1000 ->  499,500

The written code always does all n(n-1)/2 comparisons, even on an already-sorted list - the O(n) best case in the table below requires an extra optimization. Add a flag that records whether any swap happened during a pass, and stop when a pass makes none. On sorted input the first pass swaps nothing, so the sort finishes after n - 1 comparisons, which is O(n).

Key idea: bubble sort swaps adjacent out-of-order pairs pass by pass, doing n(n-1)/2 comparisons; it is O(n^2) time and O(1) space, and only reaches its O(n) best case if you add the early-exit flag.

Insertion sort

Insertion sort builds the sorted list one item at a time. It takes each element and inserts it into its correct spot among the already-sorted elements to its left, shifting larger ones right to open a gap. This is exactly how most people sort a hand of playing cards: pick up the next card and slide it into place among the cards already in order.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]   # shift right
            j = j - 1
        a[j + 1] = key        # drop key into place
    return a

Key idea: insertion sort grows a sorted prefix by sliding each new element back into place, like sorting playing cards in your hand.

Worked example: insertion sort on six numbers

Sort [5, 2, 4, 6, 1, 3]. The bar shows the boundary between the sorted prefix and the untouched rest; key is the element being placed:

start          5 | 2  4  6  1  3

i=1  key=2     compare 5>2 shift; j hits -1
               2  5 | 4  6  1  3      1 comparison, 1 shift

i=2  key=4     compare 5>4 shift; compare 2>4 no, stop
               2  4  5 | 6  1  3      2 comparisons, 1 shift

i=3  key=6     compare 5>6 no, stop
               2  4  5  6 | 1  3      1 comparison, 0 shifts

i=4  key=1     6>1, 5>1, 4>1, 2>1 all shift; j hits -1
               1  2  4  5  6 | 3      4 comparisons, 4 shifts

i=5  key=3     6>3, 5>3, 4>3 shift; 2>3 no, stop
               1  2  3  4  5  6       4 comparisons, 3 shifts

TOTAL: 12 comparisons, 9 shifts

Nine shifts is not a coincidence. An inversion is a pair of positions i < j whose values are out of order. Count them in the original array: 5 is above 2, 4, 1, and 3 (four inversions); 2 is above 1; 4 is above 1 and 3; 6 is above 1 and 3. That is 4 + 1 + 2 + 2 = nine inversions, exactly the number of shifts. Each shift moves one element past one larger element, which destroys exactly one inversion, and the array is sorted precisely when zero remain.

That gives the sharpest statement of insertion sort's cost: it runs in O(n + I) time, where I is the number of inversions. Everything else follows as a special case:

• Best case, already sorted: I = 0, so n - 1 comparisons and no shifts. O(n).
• Worst case, reverse sorted: every pair is inverted, I = n(n-1)/2. O(n^2). For n = 6 that is 15 shifts.
• Average case, random order: each pair is inverted with probability 1/2, so the expected I is n(n-1)/4 - half the worst case, same class. O(n^2).
• Nearly sorted: if no element is more than k places from home, I is at most k*n, so the sort is O(kn) - linear when k is a small constant.

Key idea: insertion sort costs one shift per inversion, so its true complexity is O(n + I); "nearly sorted" means "few inversions", which is why it is fast on such data.

Selection sort, for contrast

A third quadratic sort is worth thirty seconds because its cost profile is different in an instructive way. Selection sort scans the unsorted region for the smallest element and swaps it into place:

def selection_sort(a):
    for i in range(len(a)):
        smallest = i
        for j in range(i + 1, len(a)):
            if a[j] < a[smallest]:
                smallest = j
        a[i], a[smallest] = a[smallest], a[i]    # at most one swap per pass
    return a

It always makes n(n-1)/2 comparisons - best, average, and worst case alike, since the scan cannot stop early - so it never benefits from sorted input. But it makes at most n - 1 swaps, against insertion sort's O(n^2) shifts. That matters when moving an element is far more expensive than comparing two, as with very large records or flash memory where writes wear out the device. Selection sort in its standard array form is also not stable, because the long-distance swap can jump one equal element past another.

Key idea: selection sort is Theta(n^2) comparisons on every input but only O(n) swaps, so it wins when writes are much costlier than reads.

Why insertion sort is worth knowing

Insertion sort is O(n^2) in the worst case (a reverse-sorted list, where every element shifts all the way left), but O(n) in the best case when the list is already nearly sorted, because the inner while loop barely runs. It is in place (O(1) space) and stable, meaning it keeps equal elements in their original relative order. For small or nearly sorted arrays it beats fancier sorts, which is why real sorting libraries switch to insertion sort on small chunks.

Sort	Best	Average	Worst	Space
Bubble	O(n)	O(n^2)	O(n^2)	O(1)
Insertion	O(n)	O(n^2)	O(n^2)	O(1)

Note: bubble sort reaches its O(n) best case only with an optimization that stops early when a pass makes no swaps.

Stability deserves a concrete example, because it sounds abstract and is not. Suppose you sort a list of employees by department, then by salary. If the salary sort is stable, employees with equal salaries stay in the department order you just established, so the result is genuinely sorted by both keys. If it is unstable, that first sort is scrambled and the two-pass technique fails. Stability is what lets you sort by several keys with repeated single-key passes, cheapest key last.

Real libraries take this seriously. Python's sorted and list.sort use Timsort, which is stable and explicitly designed to exploit existing order - and it builds its initial runs with a binary insertion sort on chunks of a few dozen elements. Insertion sort is not merely tolerated inside a production sort; it is a component of one, chosen for exactly the properties in this lesson.

Key idea: insertion sort is O(n) on nearly sorted data, stable, and in place, which is why real libraries use it as the small-input engine inside a faster sort.

Where people get stuck

• "Bubble sort and insertion sort are useless." Bubble sort is mostly pedagogical, but insertion sort is genuinely fast on small or nearly sorted inputs and is used inside real libraries.
• "Best case O(n) means the sort is O(n)." The best case is a special input. The worst and average cases are O(n^2), which is what you must plan for.
• "All simple sorts are unstable." Insertion sort and bubble sort are stable; selection sort in its usual array form is not. Stability depends on whether the algorithm ever moves an element past an equal one.
• "These sorts need extra memory proportional to n." All three are in place with O(1) auxiliary space.
• Using >= instead of > in the shift test. while j >= 0 and a[j] >= key shifts equal elements too, which moves the key past its equal predecessor and quietly destroys stability. The comparison operator is the stability guarantee.
• Starting the outer loop at 0. for i in range(1, len(a)) is correct because a one-element prefix is already sorted. Starting at 0 makes the first pass compare against a[-1], which in Python is the last element - no error, just a wrong answer.
• Forgetting the empty and single-element cases. Both loops handle them correctly by doing nothing, but only because the ranges are written with len(a). Any hand-rolled bound of the form n - 1 should be checked against n = 0.

Recap

• Comparison sorts order data by comparing pairs; bubble, insertion, and selection sort are all O(n^2) in the worst case with O(1) auxiliary space.
• Bubble sort does n(n-1)/2 comparisons and needs an early-exit flag to reach its O(n) best case.
• Insertion sort performs exactly one shift per inversion, so it costs O(n + I) - O(n) when sorted, O(n^2) when reversed, and O(kn) when nothing is more than k places out of place.
• A random array has about n(n-1)/4 inversions, which is why the average case is still quadratic.
• Selection sort always makes n(n-1)/2 comparisons but at most n - 1 swaps, which suits expensive writes; it is not stable.
• Stability preserves the order of equal elements and is what makes multi-key sorting by repeated passes work; Python's Timsort is stable and uses binary insertion sort for short runs.

These sorts are the baseline the next lesson has to beat. Keep the inversion argument in mind: the reason merge sort and quicksort are faster is that they fix many inversions with a single comparison, instead of one at a time.

Sources

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Getting started: Insertion sort and analysis. In Introduction to algorithms (4th ed., ch. 2). MIT Press. find source ↗
2. Sedgewick, R., & Wayne, K. (2011). Elementary sorts. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
3. Demaine, E., Ku, J., & Solomon, J. (2020). Lecture 3: Sets and sorting. 6.006 Introduction to Algorithms, MIT OpenCourseWare. ocw.mit.edu
4. Morin, P. (2013). Sorting algorithms. In Open data structures (ch. 11). opendatastructures.org
5. Halim, S., Halim, F., & Koh, Z. C. (n.d.). Sorting: Bubble, selection, insertion, merge, quick, counting, radix. VisuAlgo, National University of Singapore. visualgo.net
6. Peters, T. (n.d.). Objects/listsort.txt: Timsort, runs, and binary insertion sort. CPython source. github.com
7. Python Software Foundation. (n.d.). Sorting techniques. Python 3 HOWTOs. docs.python.org

The big picture

Here is a puzzle worth holding in mind through this lesson. Quicksort has a worse worst case than merge sort, does more comparisons on average, and is not stable - and it is still the algorithm most standard libraries reach for. Understanding why is the difference between reciting complexity tables and being able to choose.

The big picture

The quadratic sorts are simple but too slow for large data. This lesson introduces the two great sorting algorithms that real systems rely on, both built on divide and conquer. They reach O(n log n), which is provably the best a comparison sort can do, and understanding their trade-offs lets you choose correctly and explain why Python's built-in sort is fast.

We cover merge sort, quicksort, their exact complexities including quicksort's worst case, and how to pick between them.

Why O(n log n)

The two divide-and-conquer sorts, merge sort and quicksort, reach O(n log n). The log n factor comes from repeatedly halving the problem, like folding a piece of paper: it takes only about log n folds to reduce a big sheet to a single layer. The n factor comes from doing a linear pass of work at each level. Multiply them and you get n log n, dramatically faster than n squared.

Lay the recursion tree out and the argument becomes a picture. At level 0 there is one problem of size n, and merging it costs n. At level 1, two problems of size n/2, each costing n/2 - total n. At level 2, four of size n/4 - total n again. Every level costs n, and the halving runs out after log2(n) levels:

level 0:            [ n ]                          cost n
level 1:       [n/2]     [n/2]                     cost n
level 2:    [n/4] [n/4] [n/4] [n/4]                cost n
   ...
level log2(n):  n subproblems of size 1            cost n
                                        TOTAL: n * log2(n)

So "n log n" is not a mysterious formula but a multiplication: work per level times number of levels.

And n log n is provably the floor for comparison sorts. An algorithm that only compares elements is a binary decision tree, one branch per comparison outcome. To sort correctly it must reach every one of the n! possible orderings, so the tree needs at least n! leaves; a binary tree of height h has at most 2^h leaves; so h >= log2(n!), which is Theta(n log n). Merge sort is not merely good, it is optimal. Sorts that beat the bound, like counting or radix sort, do so by looking inside the keys instead of only comparing them.

Key idea: halving the problem gives log n levels and linear work per level, so divide-and-conquer sorts are O(n log n) - and the decision-tree argument proves no comparison sort can do better.

Merge sort

Merge sort splits the list in half, recursively sorts each half, then merges the two sorted halves into one sorted list by repeatedly taking the smaller of the two front elements. The splitting creates about log n levels, and merging does O(n) work per level, so the total is O(n log n) in the best, average, and worst case alike, which makes merge sort wonderfully predictable.

def merge_sort(a):
    if len(a) <= 1:                 # base case
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left, right)

def merge(left, right):
    result, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([5, 2, 9, 1, 7]))   # [1, 2, 5, 7, 9]

The cost of that guarantee is memory: merging builds new lists, so merge sort uses O(n) auxiliary space.

It is also stable, preserving the order of equal elements - and you can see exactly which line guarantees that. The test is left[i] <= right[j]. On a tie it takes from the left half, which held the earlier elements, so equal items keep their original order. Change that <= to < and merge sort becomes unstable, with no other symptom.

Trace the merge of [2, 5, 9] and [1, 7] to see the linear pass:

left=[2,5,9] i=0   right=[1,7] j=0   result=[]
  2 <= 1 ? no  -> take 1 from right   result=[1]        j=1
  2 <= 7 ? yes -> take 2 from left    result=[1,2]      i=1
  5 <= 7 ? yes -> take 5 from left    result=[1,2,5]    i=2
  9 <= 7 ? no  -> take 7 from right   result=[1,2,5,7]  j=2 (right exhausted)
  extend with the rest of left        result=[1,2,5,7,9]

Four comparisons placed five elements. Merging lists of size p and q costs at most p + q - 1 comparisons, because every comparison consumes one element permanently. That is the "linear work per level" the recursion tree assumed.

Key idea: merge sort is a stable, always O(n log n) sort, at the cost of O(n) extra memory for merging - and the <= in the merge comparison is what makes it stable.

Quicksort

Quicksort picks a pivot element and partitions the list so that everything smaller than the pivot comes before it and everything larger comes after. After partitioning, the pivot sits in its final sorted position; quicksort then recurses on the two sides. Think of the pivot as a value that splits a crowd into "shorter than me" on the left and "taller than me" on the right, then repeats within each group. With balanced partitions it is O(n log n) on average and typically the fastest sort in practice, because it works in place with small constant factors.

Its weakness is the worst case: O(n^2), which occurs when the pivot is consistently the smallest or largest element (for example, an already-sorted list with a naive first-element pivot), so the partitions are maximally unbalanced, one side empty and the other holding everything. Good implementations avoid this by choosing the pivot randomly or as the median of a few samples, making the worst case extremely unlikely. Quicksort uses O(log n) space on average for its recursion and is usually not stable.

Key idea: quicksort partitions around a pivot for O(n log n) average speed in place, but bad pivots give an O(n squared) worst case.

Worked example: quicksort on [5, 3, 8, 1, 9, 2]

Use the Lomuto scheme, which takes the last element as the pivot and sweeps a single index across the range:

def partition(a, lo, hi):
    pivot = a[hi]
    i = lo - 1                      # end of the "<= pivot" region
    for j in range(lo, hi):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i+1], a[hi] = a[hi], a[i+1]   # drop the pivot into place
    return i + 1

def quicksort(a, lo=0, hi=None):
    if hi is None: hi = len(a) - 1
    if lo < hi:
        p = partition(a, lo, hi)
        quicksort(a, lo, p - 1)
        quicksort(a, p + 1, hi)
    return a

Now the trace. The array is [5, 3, 8, 1, 9, 2]:

CALL 1  range 0..5   pivot = 2 (last)   i = -1
  j=0  5 <= 2? no       j=1  3 <= 2? no      j=2  8 <= 2? no
  j=3  1 <= 2? YES  i=0, swap a0,a3      -> [1, 3, 8, 5, 9, 2]
  j=4  9 <= 2? no
  place pivot: swap a1, a5               -> [1, 2, 8, 5, 9, 3]  pivot at 1
  5 comparisons.  Left = [1], right = [8, 5, 9, 3]

CALL 2  range 0..0   single element, done.

CALL 3  range 2..5   pivot = 3 (last)   i = 1
  j=2  8 <= 3? no       j=3  5 <= 3? no      j=4  9 <= 3? no
  place pivot: swap a2, a5               -> [1, 2, 3, 5, 9, 8]  pivot at 2
  3 comparisons.  Left = empty, right = [5, 9, 8]

CALL 4  range 3..5   pivot = 8 (last)   i = 2
  j=3  5 <= 8? YES  i=3, swap a3,a3 (no move)
  j=4  9 <= 8? no
  place pivot: swap a4, a5               -> [1, 2, 3, 5, 8, 9]  pivot at 4
  2 comparisons.  Left = [5], right = [9]

RESULT [1, 2, 3, 5, 8, 9] in 10 comparisons.

Two details are worth extracting. A pivot lands in its final position and is never moved again - that is the invariant quicksort rests on, and why the recursive calls exclude index p. And the partitions here were poor: 2 split the array into 1 and 4, 3 split its range into 0 and 3. Even so, 10 comparisons beat insertion sort's 12 on the same data, and the advantage widens rapidly with n.

Now the worst case. Run this same code on the already-sorted [1, 2, 3, 4, 5, 6]. The pivot is always the largest element, so every partition returns hi: the left side holds n - 1 elements and the right side none. The comparison count becomes:

T(n) = T(n-1) + (n-1)
     = (n-1) + (n-2) + ... + 1 = n(n-1)/2      -> O(n^2)

The recursion depth also becomes n rather than log n, so a sorted list of 5000 items gives Python a RecursionError as well as quadratic time. Sorted input is not exotic - it is the single most common shape real data arrives in - which is why a naive first-or-last-element pivot is a genuine bug and not a theoretical curiosity.

Key idea: partitioning fixes one element permanently; a pivot that is always extreme gives partitions of size n-1 and 0, summing to n(n-1)/2 comparisons and O(n) recursion depth.

Fixing the pivot

Three defences, in increasing order of strength:

• Random pivot. Swap a random element into the pivot slot before partitioning. No input can defeat you any more, because the behaviour now depends on your random numbers rather than on the data. Expected time becomes O(n log n) for every input.
• Median of three. Take the median of the first, middle, and last elements. Cheap, and it turns the sorted-input disaster into a balanced split, though a crafted input can still defeat it.
• Introsort. Track the recursion depth and switch to heapsort once it exceeds about 2*log2(n), keeping quicksort's speed in the normal case and heapsort's guarantee in the bad one. This is what C++ std::sort does.

One more trap: arrays with many duplicate keys. Lomuto partitioning on an array where every element is equal puts all of them on one side, reproducing the O(n^2) worst case on input that looks harmless. The fix is three-way partitioning - less-than, equal-to, and greater-than regions, recursing only on the outer two - which turns quadratic into linear on data with few distinct values.

Key idea: randomize or median-select the pivot, cap the recursion depth, and use three-way partitioning when duplicates are likely.

Choosing between them

Sort	Average	Worst	Space	Stable?
Merge sort	O(n log n)	O(n log n)	O(n)	Yes
Quicksort	O(n log n)	O(n^2)	O(log n)	No

Use merge sort when you need a guaranteed O(n log n) or a stable sort, or when sorting linked lists. Use quicksort when average speed and low memory matter most. Python's built-in sorted() uses Timsort, a hybrid of merge sort and insertion sort that is O(n log n) and stable.

So return to the puzzle. Randomized quicksort makes about 1.39*n*log2(n) comparisons on average, nearly 40 percent more than merge sort's roughly n*log2(n) - and it usually still wins on an array, for three reasons that Big-O cannot show. It allocates nothing, partitioning in place. Its cache behaviour is ideal, because partitioning is a sequential sweep across one contiguous block, while merging reads two streams and writes a third. And its inner loop is tiny: one comparison and a possible swap.

The picture inverts as soon as the assumptions change. On a linked list, quicksort loses its in-place advantage and merge sort becomes natural, needing only O(log n) stack. On data too large for memory, merge sort's sequential streaming is what disks and networks want, which is why external sorts are merge sorts. And when stability is required, merge sort is the one that provides it.

Timsort is the practical synthesis, and it is what runs when you call sorted(). It scans for natural runs of already-ordered elements, extends short ones with binary insertion sort, and merges runs under a rule that keeps the merge tree balanced. On sorted or reverse-sorted input it finds one giant run and finishes in O(n) - a best case pure merge sort does not have - while keeping the O(n log n) worst case and stability.

Key idea: pick merge sort for guarantees, stability, linked lists, and external data; pick quicksort for in-memory arrays where constants and cache dominate; Timsort blends both and exploits existing order.

Where people get stuck

• "Quicksort is always faster than merge sort." On arrays it usually is, despite doing about 39 percent more comparisons, because it allocates nothing and streams through cache. On linked lists or external data, merge sort wins.
• "Merge sort sorts in place." It does not on arrays; merging allocates, so it needs O(n) auxiliary space. On a linked list it does merge in place, using only O(log n) stack.
• "A random pivot changes quicksort's average complexity." It stays O(n log n) on average; randomization moves the randomness from the input to the algorithm. The O(n^2) case still exists, it just cannot be provoked.
• "All fast sorts are stable." Merge sort and Timsort are stable; in-place quicksort and heapsort are not.
• Sorting an already-sorted array with a fixed pivot. The most common quicksort bug, producing the worst case on the most common input shape.
• Slicing in the recursive calls. The teaching version of merge sort above uses a[:mid], which copies. Fine for learning, wasteful in production, where you pass indices into one shared buffer.

Recap

• Divide-and-conquer sorts halve the problem (log2(n) levels) and do linear work per level, giving O(n log n).
• The decision-tree bound - at least n! leaves, so height at least log2(n!) - proves no comparison sort beats Omega(n log n).
• Merge sort is O(n log n) in every case and stable, but uses O(n) extra memory on arrays; merging p and q elements costs at most p + q - 1 comparisons.
• Quicksort partitions around a pivot, fixing it permanently, and is O(n log n) on average in place with O(log n) stack.
• An always-extreme pivot gives partitions of n-1 and 0, costing n(n-1)/2 comparisons and O(n) depth; randomization, median-of-three, or introsort prevent it, and three-way partitioning handles duplicates.
• Quicksort usually wins on arrays despite more comparisons, because of in-place partitioning and cache locality; Python's Timsort is stable, exploits natural runs, and is O(n) on sorted input.

If you remember one sentence from this lesson, make it this: the complexity table tells you which algorithms are viable, and the memory behaviour tells you which one to ship.

Sources

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Merge sort; Quicksort; Lower bounds for sorting. In Introduction to algorithms (4th ed., chs. 2, 7, 8). MIT Press. find source ↗
2. Hoare, C. A. R. (1962). Quicksort. The Computer Journal, 5(1), 10-16. find source ↗
3. Sedgewick, R., & Wayne, K. (2011). Mergesort. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
4. Sedgewick, R., & Wayne, K. (2011). Quicksort: Three-way partitioning and pivot selection. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
5. Peters, T. (n.d.). Objects/listsort.txt: Timsort design notes on runs, galloping, and merge order. CPython source. github.com
6. Morin, P. (2013). Sorting algorithms: Merge sort, quicksort, and the lower bound. In Open data structures (ch. 11). opendatastructures.org
7. Halim, S., Halim, F., & Koh, Z. C. (n.d.). Sorting: Merge sort and quicksort visualizations. VisuAlgo, National University of Singapore. visualgo.net

The big picture

Jon Bentley reported that in his courses, roughly nine out of ten professional programmers failed to write a correct binary search when given a couple of hours. The idea takes one sentence; the boundary conditions take real care. That gap - simple concept, brutal details - is exactly why this algorithm is worth a full lesson.

The big picture

Binary search is the payoff for keeping data sorted: it finds any value in a sorted collection almost instantly, even among millions of items. It is also the cleanest example of logarithmic time you will meet, and the same halving idea drives balanced trees and many other fast algorithms. Learning to implement it correctly is a rite of passage in computer science.

This lesson explains why sorting is required, implements binary search, traces it on a small array, and proves its O(log n) cost.

What binary search does

Binary search finds a target in a sorted array in O(log n) time, a dramatic improvement over the O(n) of scanning every element (a linear search). It works by repeatedly halving the search range. Compare the target with the middle element: if they match, you are done; if the target is smaller, the answer can only be in the left half; if larger, only in the right half. Each comparison throws away half of what remains. It is exactly how you guess a number in a sorted phone book: open to the middle, decide which half the name is in, and repeat.

Key idea: binary search halves a sorted range each comparison, like flipping to the middle of a phone book, giving O(log n) time.

Why sorted, and why it is fast

Binary search depends entirely on order: only in a sorted array can one comparison with the middle rule out an entire half. If the data were unsorted, the middle element would tell you nothing about where the target lies. Starting from n items, halving repeatedly gives the sequence n, n/2, n/4, and so on down to 1. The number of halvings is about log base 2 of n. Searching a sorted array of a million items takes only about 20 comparisons, versus up to a million for a linear scan.

Make the counting exact. After k iterations the surviving range has at most n / 2^k elements, and the loop must stop when that drops below 1. Solving n / 2^k < 1 gives k > log2(n), so the worst case is floor(log2(n)) + 1 iterations:

n                  worst-case iterations
6                          3
1,000                     10
1,000,000                 20
1,000,000,000             30
1,000,000,000,000         40

Read that column again. A thousand-fold increase in the data adds ten comparisons. This is the practical meaning of "logarithmic": the algorithm barely notices how much data you have, and it is why sorted structures dominate databases and file systems.

Binary search also needs random access, not just order. Computing the midpoint has to be O(1), which an array gives and a linked list does not - walking to the middle of a linked list is already O(n), so binary search on one costs O(n) and gains nothing. This is precisely the gap that binary search trees exist to close, by encoding the halving in the structure instead of in arithmetic.

Key idea: sorting is the precondition that lets one comparison eliminate half the data, and O(1) indexing is the second precondition; together they give floor(log2(n)) + 1 comparisons in the worst case.

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid            # found it
        elif a[mid] < target:
            lo = mid + 1          # search right half
        else:
            hi = mid - 1          # search left half
    return -1                     # not present

nums = [1, 3, 5, 7, 9, 11]
print(binary_search(nums, 9))     # 4
print(binary_search(nums, 4))     # -1

Tracing it step by step

Search for 9 in [1, 3, 5, 7, 9, 11], indices 0 to 5.

• Start: lo = 0, hi = 5, so mid = 2. Value at index 2 is 5, which is less than 9, so the target is to the right. Set lo = 3.
• Next: lo = 3, hi = 5, so mid = 4. Value at index 4 is 9, a match. Return 4.

Just two comparisons instead of five. If we had searched for 4, the range would shrink until lo passes hi, and the function returns -1 to mean "not present."

The failed search is the one worth tracing in full, because that is where the boundary logic earns its keep. Search for 4 in the same array:

step  lo  hi  mid  a[mid]  decision              new range
  1    0   5   2     5     5 > 4, go left        lo=0, hi=1
  2    0   1   0     1     1 < 4, go right       lo=1, hi=1
  3    1   1   1     3     3 < 4, go right       lo=2, hi=1
  4   lo (2) > hi (1)  -> loop ends, return -1

Three iterations, matching floor(log2(6)) + 1 = 3. Notice step 3: the range had collapsed to a single element, and the algorithm still had to examine it. A common bug is writing while lo < hi instead of while lo <= hi, which skips that final check and reports "not found" for any target sitting in the last surviving slot.

Notice too that both branches move the boundary past mid: lo = mid + 1, not lo = mid. With lo = mid, a two-element range where lo = 0 and hi = 1 gives mid = 0 forever, and the loop never terminates. Every binary search must guarantee the range strictly shrinks on every iteration; the plus and minus one are that guarantee, not decoration.

Key idea: tracking lo, hi, and mid, each step either finds the target or discards one half - and correctness rests on two things, that the loop condition includes the single-element case and that each update moves strictly past mid.

The overflow bug that lived for two decades

The line mid = (lo + hi) // 2 is correct in Python and wrong in most other languages. In a language with fixed-width integers, lo + hi can exceed the maximum before the division happens, wrapping around to a negative number and producing an array index that either crashes or reads garbage. It needs an array of more than about a billion elements in 32-bit Java, which is why the bug hid for so long.

# Python: integers are arbitrary precision, so both are safe
mid = (lo + hi) // 2

# The overflow-proof form, and the one to write by habit:
mid = lo + (hi - lo) // 2

The second version can never overflow, because hi - lo is at most the array length. Joshua Bloch documented this in 2006 after finding it in the JDK's own binarySearch - code that had been published, reviewed, and formally verified in a textbook, and had shipped for nine years. Two lessons: verified pseudocode can still be a buggy program, because the proof assumed mathematical integers; and boundary arithmetic deserves suspicion even when the logic is obviously right.

Key idea: write lo + (hi - lo) // 2 as a reflex; the naive midpoint overflows in fixed-width arithmetic and hid in production code for nine years.

Cost summary

Binary search is O(log n) time. Written iteratively as above it uses O(1) space (just the index variables); written recursively it uses O(log n) stack space. The one requirement is that the data is sorted. So if you will search a collection many times, sorting it once (O(n log n)) to enable fast repeated binary searches is a common and worthwhile trade.

Do the arithmetic on that trade. Sorting costs about n*log2(n) and each binary search costs log2(n), against n for a linear scan. Sorting pays for itself once the number of searches k satisfies n*log2(n) + k*log2(n) < k*n, which for n = 1,000,000 happens at roughly k = 21. Below that, scan; above it, sort once. And if the collection changes constantly, a hash table (O(1) lookup, no ordering cost) or a balanced tree (O(log n) lookup and O(log n) insert) beats re-sorting an array after every change.

Key idea: iterative binary search is O(log n) time and O(1) space; sorting once pays off after a couple of dozen searches, and a tree or hash table wins when the data keeps changing.

Use the library, and know what it returns

Python's bisect module is a tested binary search, and it answers a more useful question than "is it present". bisect_left returns the index where the value would be inserted to keep the list sorted, placing it before any equal elements; bisect_right places it after:

from bisect import bisect_left, bisect_right, insort

a = [1, 3, 3, 3, 5]
bisect_left(a, 3)      # 1  - first index where 3 could go
bisect_right(a, 3)     # 4  - one past the last 3
bisect_right(a, 3) - bisect_left(a, 3)   # 3  - how many 3s there are
bisect_left(a, 4)      # 4  - first element >= 4 is a[4] == 5
insort(a, 4)           # [1, 3, 3, 3, 4, 5]  (O(log n) search, O(n) insert)

Those two functions cover most real uses: counting duplicates, finding the first element at least as large as x, locating a range, or checking presence with i < len(a) and a[i] == x. Note that insort finds the position in O(log n) but still shifts elements in O(n), so building a sorted list by repeated insertion is O(n^2) - sort once at the end instead.

The deepest use of the idea is binary search on the answer. Whenever a yes/no question is monotonic - false, false, ..., false, true, true, ... - you can binary search for the boundary even when there is no array at all. "What is the smallest number of shipping days that fits this workload?" or "What is the largest buffer that stays under the memory limit?" are answered in O(log R) evaluations of the predicate over a range of size R. Recognizing monotonicity is the skill; the search itself is the same ten lines.

Key idea: bisect_left and bisect_right answer "where does it belong", which is more useful than "is it there" - and any monotonic predicate can be binary searched, array or not.

Where people get stuck

• "Binary search works on any array." It requires sorted data and O(1) indexing. On unsorted data the midpoint comparison gives no information; on a linked list, finding the midpoint is already O(n).
• "It is O(1) because it jumps to the middle." Each step is O(1), but it takes up to floor(log2(n)) + 1 steps, so the total is O(log n).
• "Sorting first is never worth it." For one search, scan. For dozens on stable data, sort once. For constant change, use a hash table or a balanced tree.
• "Recursive binary search is also O(1) space." The recursive version uses O(log n) stack space; only the iterative version is O(1).
• The off-by-one at the loop condition. With hi = len(a) - 1 the interval is closed and the loop must be while lo <= hi. With hi = len(a) the interval is half-open and the loop must be while lo < hi with hi = mid. Mixing the two conventions is the single most common way to break it - pick one and keep it consistent.
• The infinite loop. If an update assigns lo = mid in a closed-interval search, a two-element range recomputes the same mid forever. Every branch must exclude mid.
• The midpoint overflow. (lo + hi) // 2 is safe only where integers are unbounded. Prefer lo + (hi - lo) // 2 everywhere.
• Empty input. With len(a) == 0 we get lo = 0 and hi = -1, so the loop body never runs and the function returns -1. Correct, but only by accident of the initialization - check it deliberately when you write your own.

Recap

• Binary search finds a target in a sorted, randomly accessible array in O(log n) by halving the range each comparison.
• The worst case is floor(log2(n)) + 1 iterations: 20 for a million elements, 30 for a billion.
• Correctness needs a loop condition that covers the single-element range and updates that move strictly past mid, or the search either misses values or loops forever.
• Write the midpoint as lo + (hi - lo) // 2; the naive form overflows in fixed-width integer languages and shipped broken in the JDK for nine years.
• Iterative binary search is O(1) space, the recursive form O(log n); sorting to enable searching pays off after roughly a couple of dozen queries.
• bisect_left and bisect_right give insertion points, which answer counting and range questions; any monotonic predicate can be binary searched even without an array.

Write it from memory once a year. The version you can produce under pressure, with the boundaries right, is worth more than the version you can recognize.

Sources

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Getting started: Binary search and loop invariants. In Introduction to algorithms (4th ed., ch. 2). MIT Press. find source ↗
2. Bloch, J. (2006). Extra, extra - read all about it: Nearly all binary searches and mergesorts are broken. Google Research Blog. research.google
3. Python Software Foundation. (n.d.). bisect - Array bisection algorithm. Python 3 documentation. docs.python.org
4. Sedgewick, R., & Wayne, K. (2011). Elementary symbol tables: Binary search in an ordered array. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
5. cp-algorithms contributors. (n.d.). Binary search. Algorithms for Competitive Programming. cp-algorithms.com
6. Demaine, E., Ku, J., & Solomon, J. (2020). Lecture notes: Binary search and logarithmic time. 6.006 Introduction to Algorithms, MIT OpenCourseWare. ocw.mit.edu
7. Malan, D. J. (2025). Lecture 3: Algorithms: Linear and binary search. CS50x, Harvard University. cs50.harvard.edu

The big picture

A sorted array gives you O(log n) search but O(n) insertion. A linked list gives you O(1) insertion but O(n) search. The binary search tree is the structure that refuses to choose: it keeps data in order and lets you change it, both in logarithmic time - provided you keep it in shape, which is the whole story of this lesson.

The big picture

Trees bring hierarchy to data, and the binary search tree brings order to that hierarchy so you can search, insert, and delete in logarithmic time. Trees sit between the instant-but-unordered hash table and the ordered-but-rigid sorted array, and they are the foundation for balanced trees, heaps, and much of what databases and file systems do.

This lesson defines tree vocabulary, states the binary search tree ordering rule, and explains why performance depends on the tree's shape.

Tree vocabulary

A tree is a hierarchical structure of nodes connected by edges, with no cycles, like a family tree or a company org chart. One node is the root at the top (the founder of the family). Each node may have children below it; a node with no children is a leaf (the newest generation). The height of a tree is the number of edges on the longest path from the root down to a leaf, in other words how many levels deep the tree goes. Trees model hierarchy everywhere: file systems, family trees, and the decision structure of many algorithms.

Key idea: a tree is an acyclic hierarchy with one root at the top and leaves at the bottom; its height is the longest root-to-leaf path.

Binary trees

A binary tree restricts each node to at most two children, conventionally called left and right. Here is a node definition:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Key idea: a binary tree gives each node at most a left and a right child.

The binary search tree property

A binary search tree (BST) is a binary tree with an ordering rule: for every node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater. This invariant makes search behave exactly like binary search: to find a value, compare it with the current node and go left if smaller or right if larger, discarding the other subtree each step. It is the phone-book halving idea built directly into the structure of the data.

def bst_insert(root, value):
    if root is None:
        return TreeNode(value)
    if value < root.value:
        root.left = bst_insert(root.left, value)
    else:
        root.right = bst_insert(root.right, value)
    return root

def bst_search(root, value):
    if root is None or root.value == value:
        return root
    if value < root.value:
        return bst_search(root.left, value)
    return bst_search(root.right, value)

Key idea: in a BST every left subtree holds smaller values and every right subtree holds larger, so search discards half the tree at each step.

Read the invariant precisely, because the sloppy version causes a classic bug. It is not "left child smaller, right child larger" - it is "every value in the entire left subtree is smaller". A validator that only compares each node with its immediate parent will happily accept a tree that is not a BST. Correct validation passes a permitted range down the recursion: the left child inherits an upper bound of the parent's value, the right child inherits a lower bound.

Worked example: building and searching a BST

Insert 50, 30, 70, 20, 40, 60, 80 in that order, following the rule "go left if smaller, right if larger, and hang off the first empty slot you find":

insert 50   root is empty                     50
insert 30   30 < 50, go left, empty           50 -> L:30
insert 70   70 > 50, go right, empty          50 -> R:70
insert 20   20 < 50 left; 20 < 30 left        30 -> L:20
insert 40   40 < 50 left; 40 > 30 right       30 -> R:40
insert 60   60 > 50 right; 60 < 70 left       70 -> L:60
insert 80   80 > 50 right; 80 > 70 right      70 -> R:80

                50
             /      \
           30        70
          /  \      /  \
        20    40  60    80

Seven nodes, height 2, perfectly balanced. Now search for 40: compare with 50 (smaller, go left), compare with 30 (larger, go right), compare with 40 (found). Three comparisons, one per level - and the tree at height 2 can hold at most 7 nodes, so log2(7 + 1) = 3 comparisons is the bound.

Now insert 10, 20, 30, 40 into an empty tree, in that order:

10
  \
   20
     \
      30
        \
         40        height 3 with only 4 nodes - a linked list wearing a hat

Every value is larger than the last, so every insertion goes right, and the tree degenerates. Searching for 40 now costs 4 comparisons rather than 3, and the gap widens without limit: at n = 1,000,000 a balanced tree costs 20 comparisons and this chain costs a million. Sorted input is the natural enemy of a naive BST, the same way it is for a naive quicksort pivot, and for the same reason - the structure's balance depends on the input order.

Key idea: a BST's shape is determined by insertion order, and sorted input produces a chain of height n instead of a tree of height log2(n).

Deletion: the operation with three cases

Search and insert are easy because they only ever add a leaf. Deletion has to preserve the ordering invariant while removing a node that may have children, and it splits into three cases:

def bst_delete(root, value):
    if root is None:
        return None
    if value < root.value:
        root.left = bst_delete(root.left, value)
    elif value > root.value:
        root.right = bst_delete(root.right, value)
    else:
        # CASE 1: no children - just drop it
        # CASE 2: one child - splice the child in
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        # CASE 3: two children - replace with the in-order successor
        succ = root.right
        while succ.left is not None:      # smallest value on the right
            succ = succ.left
        root.value = succ.value
        root.right = bst_delete(root.right, succ.value)
    return root

Case 3 is the interesting one. To remove a node with two children you cannot simply promote one of them; instead you overwrite its value with its in-order successor, the smallest value in the right subtree, then delete that successor from the right subtree. The successor is the only value that can sit in that position without breaking the invariant, because it is larger than everything on the left and smaller than everything else on the right. It also has at most one child by construction - it is the leftmost node of its subtree - so removing it falls into case 1 or 2 and the recursion terminates.

Trace deleting 30 from the balanced tree above. Node 30 has children 20 and 40, so this is case 3. The successor is the leftmost node of 30's right subtree, which is 40. Copy 40 into the node, then delete the original 40, a leaf:

                50                      50
             /      \                 /      \
           30        70    --->     40        70
          /  \      /  \           /         /  \
        20    40  60    80       20        60    80

Deletion costs one descent to find the node plus one descent to find the successor, both bounded by the height: O(h), which is O(log n) balanced and O(n) degenerate, like every other BST operation.

Key idea: deleting a node with two children means promoting its in-order successor, which is guaranteed to have at most one child, so the recursion always bottoms out in the easy cases.

Complexity depends on shape

Each step down a BST discards one subtree, so search, insert, and delete all cost time proportional to the tree's height. In a balanced BST, one whose left and right sides stay roughly even, the height is about log n, giving O(log n) operations.

The bound is easy to derive. A binary tree of height h has at most 1 + 2 + 4 + ... + 2^h = 2^(h+1) - 1 nodes, one full level at a time. Turn that around: to hold n nodes you need 2^(h+1) - 1 >= n, so h >= log2(n + 1) - 1. No binary tree of n nodes can be shorter than about log2(n), and a balanced one achieves it. The height is not a lucky property; it is the minimum the arithmetic allows.

But if you insert already-sorted data into a naive BST, each new value goes to the same side and the tree degenerates into a long chain (essentially a linked list) of height n, giving O(n), the worst case. This is why self-balancing trees such as AVL and red-black trees exist: they perform small rearrangements called rotations to keep the height near log n and guarantee O(log n) operations.

Between those extremes sits a reassuring result. If the n keys arrive in a random order, the expected height of the resulting BST is about 4.3 * ln(n), roughly three times log2(n) - still Theta(log n). Random data builds a decent tree on its own; the disasters come from ordered or nearly ordered input. There is a pleasing connection here: inserting a random permutation into a BST performs exactly the same comparisons as running quicksort on that permutation, with each node playing the role of a pivot. The two algorithms have the same average-case analysis because they are, structurally, the same process.

The self-balancing variants make the guarantee unconditional. An AVL tree keeps the heights of a node's two subtrees within 1 of each other, giving a height under 1.44*log2(n), and pays for it with more rotations on insert. A red-black tree allows a looser balance, height under 2*log2(n + 1), and rotates less - which is why it backs C++ std::map, Java TreeMap, and the Linux kernel scheduler. Both do their work with rotations, a constant-time relink of three nodes that changes the shape without disturbing the in-order sequence.

Operation	Balanced BST	Unbalanced (worst)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

Space is O(n) to store n nodes. A BST keeps data sorted and supports fast ordered operations, filling the gap between the O(1) unordered lookup of a hash table and the ordered-but-static nature of a sorted array.

Key idea: BST operations cost time proportional to height, so a balanced tree is O(log n) but a degenerate chain is O(n); random insertion order gives Theta(log n) height on its own, and balanced variants guarantee it for any order.

Where people get stuck

• "A BST is always O(log n)." Only when balanced. Inserting sorted data naively builds a chain with O(n) operations - and sorted input is common, not exotic.
• "Any binary tree is a binary search tree." A BST additionally obeys the ordering rule; a plain binary tree need not.
• Validating against the parent only. Checking that each node is greater than its left child and less than its right child is not enough. A node deep in the left subtree can still exceed an ancestor. Pass a (min, max) range down the recursion instead.
• "Trees can have cycles." By definition a tree is acyclic; a structure with cycles is a general graph.
• "A hash table can replace a BST for everything." Hash tables give O(1) lookup but no order. A BST supports sorted traversal, range queries, and nearest-neighbour lookups, none of which a hash table can do without scanning everything.
• Not deciding what duplicates mean. The insert code above sends equal values right, which permits duplicates. Other designs reject them or keep a count per node. Pick one deliberately, because search, delete, and traversal all behave differently under each.
• Deleting the root. The recursive delete returns the new subtree root, so the caller must write root = bst_delete(root, x). Ignoring the return value silently leaves a stale root when the root itself is removed.
• Recursion depth on a degenerate tree. A chain of 5000 nodes makes recursive search hit Python's frame limit. Balanced trees are safe at any realistic n, since even a billion nodes is about 60 frames deep.

Recap

• A tree is an acyclic hierarchy with a root and leaves; height is the longest root-to-leaf path.
• A binary tree has at most two children per node; a BST adds the rule that the whole left subtree is smaller and the whole right subtree larger.
• A binary tree of height h holds at most 2^(h+1) - 1 nodes, so any tree of n nodes has height at least log2(n + 1) - 1.
• Search, insert, and delete all cost O(h): O(log n) balanced, O(n) for the chain that sorted input produces.
• Deleting a node with two children promotes its in-order successor, the leftmost node of the right subtree, which has at most one child.
• Random insertion order gives an expected height of about 4.3*ln(n); AVL trees guarantee under 1.44*log2(n) and red-black trees under 2*log2(n + 1) using rotations.

Reach for a tree when you need order and change at the same time. If you need only one of those, a sorted array or a hash table will be simpler and faster.

Sources

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Binary search trees; Red-black trees. In Introduction to algorithms (4th ed., chs. 12-13). MIT Press. find source ↗
2. Sedgewick, R., & Wayne, K. (2011). Binary search trees. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
3. Sedgewick, R., & Wayne, K. (2011). Balanced search trees: 2-3 trees and red-black BSTs. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
4. Morin, P. (2013). Binary trees. In Open data structures (ch. 6). opendatastructures.org
5. Morin, P. (2013). Random binary search trees. In Open data structures (ch. 7). opendatastructures.org
6. Demaine, E., Ku, J., & Solomon, J. (2020). Lecture 7: Binary trees, part 2 - AVL. 6.006 Introduction to Algorithms, MIT OpenCourseWare. ocw.mit.edu
7. Halim, S., Halim, F., & Koh, Z. C. (n.d.). Binary search tree, AVL tree. VisuAlgo, National University of Singapore. visualgo.net

The big picture

Three of the four traversals in this lesson differ by the position of a single line of code. Move the visit above the recursive calls, between them, or below them, and you get three completely different orders with three completely different uses - one of which sorts your data for free. Few places in programming pay so much for so small a change.

The big picture

Once you have a tree, you need a systematic way to visit every node, whether to print, copy, evaluate, or search it. Traversals are those systematic visiting orders, and choosing the right one is often the whole trick to a tree algorithm. One traversal even prints a binary search tree in perfect sorted order for free.

This lesson covers the three depth-first orders, the breadth-first level order, and which task each one fits.

What a traversal is

A traversal visits every node of a tree exactly once in a defined order. There are two families: depth-first traversals that plunge down one branch as far as possible before backing up, and breadth-first traversal that sweeps across the tree level by level. All of them visit n nodes, so every traversal is O(n) time. Depth-first is like exploring a building by following one hallway to its end before trying another; breadth-first is like checking every room on floor one before going up to floor two.

Key idea: a traversal visits each of the n nodes exactly once in a chosen order, so every traversal is O(n).

The time is identical; the space is not, and this surprises people. A recursive depth-first traversal keeps one frame per level, so it uses O(h) space - about log2(n) on a balanced tree, but O(n) on a degenerate chain. A level-order traversal keeps a queue holding an entire level at once, so it uses O(w) space where w is the widest level. In a complete binary tree the bottom level holds about half the nodes, so level-order costs roughly n/2 - O(n). On wide trees, breadth-first uses far more memory than depth-first, which is exactly the opposite of most people's intuition and matters again in Lesson 16.

The three depth-first orders

Depth-first traversals differ only in when they visit the current node relative to its two subtrees:

• In-order: left subtree, then node, then right subtree.
• Pre-order: node, then left subtree, then right subtree.
• Post-order: left subtree, then right subtree, then node.

def in_order(node):
    if node is None:
        return
    in_order(node.left)
    print(node.value)      # visit between the two subtrees
    in_order(node.right)

def pre_order(node):
    if node is None:
        return
    print(node.value)      # visit before the subtrees
    pre_order(node.left)
    pre_order(node.right)

def post_order(node):
    if node is None:
        return
    post_order(node.left)
    post_order(node.right)
    print(node.value)      # visit after the subtrees

Key idea: in-order, pre-order, and post-order differ only in whether the node is visited between, before, or after its subtrees.

Worked example: all four orders on one tree

Use the balanced tree from the previous lesson:

                50
             /      \
           30        70
          /  \      /  \
        20    40  60    80

Trace in-order by hand. Start at 50 and immediately recurse left to 30, then left again to 20. Node 20 has no left child, so it is visited first. Then back up: 20, 30, 40, 50, and so on. Here are all four results:

IN-ORDER     (left, node, right)   20  30  40  50  60  70  80
PRE-ORDER    (node, left, right)   50  30  20  40  70  60  80
POST-ORDER   (left, right, node)   20  40  30  60  80  70  50
LEVEL-ORDER  (by depth, queue)     50  30  70  20  40  60  80

Check each against the shape. In-order is sorted, as promised. Pre-order starts at the root, which is why it is the format for serializing a tree - the first value you read is always the root of whatever you are rebuilding. Post-order ends at the root, which is why it is the format for deleting a tree: children are freed before their parent, so you never follow a dangling pointer. Level-order reproduces the insertion order that built this particular tree, which is a coincidence of this example and not a rule.

One further fact that looks like a puzzle and is genuinely useful: pre-order plus in-order reconstructs the tree uniquely. The first pre-order value, 50, is the root. Find 50 in the in-order list; everything to its left, [20, 30, 40], is the left subtree and everything to the right, [60, 70, 80], is the right subtree. Take the next three pre-order values, [30, 20, 40], as the left subtree's pre-order, and recurse. Neither order alone is enough - many different trees share a pre-order - and for a general binary tree, pre-order plus post-order is also insufficient, because it cannot tell a single left child from a single right child.

Key idea: pre-order names the root first and is the serialization format; post-order names it last and is the teardown order; in-order sorts a BST; and pre-order plus in-order together pin down the tree exactly.

Expression trees: why post-order is postfix

Compilers represent arithmetic as a tree with operators at the internal nodes and values at the leaves. Here is (3 + 5) * 2:

        *
       / \
      +   2
     / \
    3   5

IN-ORDER    3 + 5 * 2      ambiguous - the parentheses are gone
PRE-ORDER   * + 3 5 2      prefix (Polish) notation
POST-ORDER  3 5 + 2 *      postfix (reverse Polish) notation

In-order loses the grouping, which is exactly why written arithmetic needs parentheses. The other two orders need none, because the operator's position already says which operands it takes. Postfix in particular evaluates with nothing but a stack, one pass, left to right - push values, and on an operator pop two, combine, push the result:

token  action                         stack
  3    push 3                         [3]
  5    push 5                         [3, 5]
  +    pop 5 and 3, push 3+5          [8]
  2    push 2                         [8, 2]
  *    pop 2 and 8, push 8*2          [16]
       one value left -> answer 16

That is the whole evaluation engine of a stack-based calculator, and it is why post-order and stacks keep appearing together.

Key idea: post-order output is postfix notation, which a stack evaluates in one linear pass with no parentheses and no precedence rules.

The special power of in-order

Running an in-order traversal on a binary search tree visits the values in sorted ascending order. This is a direct consequence of the BST property: everything to the left is smaller and everything to the right is larger, so visiting left, then node, then right yields steadily increasing values. It is the cleanest way to print a BST in order, and it is why a BST plus an in-order walk acts like an always-sorted list.

Key idea: an in-order traversal of a BST outputs the keys in sorted ascending order.

Level-order traversal

Level-order traversal visits all nodes at depth 0, then all at depth 1, and so on, top to bottom and left to right. Unlike the depth-first orders, it is not naturally recursive; you implement it with a queue: enqueue the root, then repeatedly dequeue a node, visit it, and enqueue its children. This is exactly breadth-first search applied to a tree, which we generalize to arbitrary graphs in the next module.

Traversal	Order visited	Common use
In-order	Left, node, right	Print a BST in sorted order
Pre-order	Node, left, right	Copy or serialize a tree
Post-order	Left, right, node	Delete a tree or evaluate expressions
Level-order	By depth, using a queue	Shortest path in an unweighted tree

Here is the code, and note the choice of container in each case:

from collections import deque

def level_order(root):                 # BFS: queue, O(n) time, O(w) space
    if root is None: return
    q = deque([root])
    while q:
        node = q.popleft()             # popleft, NOT pop(0)
        print(node.value)
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)

def in_order_iterative(root):          # DFS without recursion
    stack, node = [], root
    while stack or node is not None:
        while node is not None:        # dive left, remembering the path
            stack.append(node)
            node = node.left
        node = stack.pop()             # nothing further left: visit
        print(node.value)
        node = node.right              # then handle the right subtree

The iterative in-order version is worth having in your toolkit for two reasons. It sidesteps Python's 1000-frame recursion limit on a degenerate tree, and it makes explicit what recursion was doing implicitly: the call stack was that list of remembered ancestors. Swap the deque for a stack in level_order and you get a depth-first traversal - the same identity we met with stacks and queues, and the one that Lesson 16 generalizes to graphs.

Key idea: level-order is breadth-first, implemented with a queue, visiting the tree depth by depth; a stack in the same loop gives depth-first instead.

Where people get stuck

• "In-order works on any binary tree to give sorted output." It gives sorted output only on a binary search tree, whose ordering rule makes the sequence increase. On an arbitrary binary tree it is just an order.
• "Level-order can be done with simple recursion like the others." Level-order naturally needs a queue. You can fake it recursively by visiting one depth at a time, but that re-walks the upper levels and costs O(n*h).
• "Different traversals have different time complexities." All visit n nodes once, so all are O(n) time. Their space differs: O(h) for depth-first, O(w) for breadth-first.
• "Breadth-first uses less memory." Usually the reverse on a tree. The queue can hold half the nodes at the widest level, while the recursion stack only holds one node per level.
• "Pre-order and post-order produce the same sequence." They differ: pre-order visits the node first, post-order visits it last. On the example tree they share no position except by coincidence.
• Forgetting the None base case. Every recursive traversal must return immediately on an empty subtree. Without it, the first leaf raises AttributeError on None.left.
• Using a list as the BFS queue. q.pop(0) shifts every remaining element, turning an O(n) traversal into O(n^2). Use deque.popleft.
• Modifying the tree during a traversal. Deleting nodes mid-walk invalidates the parents still sitting on the stack. Collect the nodes first, then act on the collected list.

Recap

• A traversal visits every node once, so all four are O(n) time; depth-first uses O(h) space and level-order uses O(w), which can be about n/2.
• In-order, pre-order, and post-order differ only by when the node is visited relative to its subtrees.
• In-order on a BST yields sorted ascending order, which is the BST property read out loud.
• Pre-order serializes a tree and post-order tears one down; pre-order plus in-order reconstructs a tree uniquely, while either alone does not.
• Post-order of an expression tree is postfix notation, evaluated by a stack in one pass with no parentheses.
• Level-order is breadth-first with a queue; replacing the queue with a stack turns it into depth-first.

When a tree problem stalls, ask which order gives you the information you need at the moment you need it. That question usually is the algorithm.

Sources

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Binary search trees: Inorder tree walk. In Introduction to algorithms (4th ed., ch. 12). MIT Press. find source ↗
2. Morin, P. (2013). Binary trees: Traversing binary trees. In Open data structures (ch. 6). opendatastructures.org
3. Sedgewick, R., & Wayne, K. (2011). Binary search trees: Ordered operations and tree traversal. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
4. Demaine, E., Ku, J., & Solomon, J. (2020). Lecture 6: Binary trees, part 1. 6.006 Introduction to Algorithms, MIT OpenCourseWare. ocw.mit.edu
5. Halim, S., Halim, F., & Koh, Z. C. (n.d.). Binary search tree, AVL tree: Traversal animations. VisuAlgo, National University of Singapore. visualgo.net
6. Python Software Foundation. (n.d.). collections: deque objects. Python 3 documentation. docs.python.org
7. Python Software Foundation. (n.d.). sys: setrecursionlimit and deep traversals. Python 3 documentation. docs.python.org

The big picture

Keeping a collection fully sorted so you can grab the smallest item is doing far too much work. You only ever look at one end, so why pay to order the other. A heap is the structure built on exactly that observation: order just enough to know the minimum, and no more.

The big picture

A heap is the structure you reach for whenever you repeatedly need the smallest or largest item from a changing collection, such as the next task to run or the nearest unvisited city in a shortest-path search. It keeps that extreme element instantly available while allowing fast inserts, and it does so with a clever array layout that uses no pointers at all.

This lesson defines the heap property and shape, connects heaps to priority queues, and states the cost of each operation.

What a heap is

A heap is a specialized binary tree that keeps the most extreme element instantly reachable. In a min-heap, every parent is less than or equal to its children, so the smallest element is always at the root. A max-heap is the mirror image, with the largest at the root.

Picture a company where every manager earns less than everyone they supervise (a min-heap): the lowest earner is guaranteed to be at the very top. A heap is only partially ordered: unlike a BST, siblings have no required order, which is why a heap cannot search for an arbitrary value quickly, but can always hand you the minimum (or maximum) in O(1).

That weaker guarantee is a feature, not a compromise. A full sort of n items costs n*log2(n) comparisons; a heap of the same items can be built in O(n), because it never has to decide the relative order of two items in different subtrees. You buy exactly the ordering you use and skip the rest.

Key idea: a heap keeps the min (or max) at the root via the parent-child ordering rule, but it is only partially ordered, so it is not for arbitrary search.

Shape and array storage

A binary heap is a complete binary tree: every level is full except possibly the last, which fills left to right with no gaps. This regular shape lets a heap be stored compactly in a plain array with no pointers. For the element at index i, its children live at indices 2i + 1 and 2i + 2, and its parent at (i - 1) // 2. Because the shape is gap-free, the array has no wasted holes, which is why heaps are both fast and memory-efficient.

Key idea: a heap is a complete (gap-free) binary tree, so it packs into an array where index arithmetic locates parents and children without pointers.

The payoff of the array layout is more than saved memory. There are no allocations per node, no pointer chasing, and the parent and children of any index are computed in one instruction each. Verify the arithmetic on a small heap and it will stick:

index:   0    1    2    3    4    5
value:   1    3    2    5    9    8

                1  (index 0)
             /     \
        3 (1)       2 (2)
       /    \      /
    5 (3)  9 (4)  8 (5)

children of index 1: 2*1+1 = 3 and 2*1+2 = 4   -> values 5 and 9
parent of index 5:   (5-1)//2 = 2              -> value 2

Priority queues

A priority queue is an abstract structure that always removes the highest-priority item next, rather than the oldest (a plain queue) or the newest (a stack). It is like an emergency room that treats the most critical patient next regardless of arrival time. Heaps are the standard way to implement one. Python's heapq module provides a min-heap over an ordinary list.

import heapq
pq = []
heapq.heappush(pq, 5)     # insert, O(log n)
heapq.heappush(pq, 1)
heapq.heappush(pq, 3)
print(pq[0])              # peek smallest -> 1, O(1)
print(heapq.heappop(pq))  # extract smallest -> 1, O(log n)
print(heapq.heappop(pq))  # -> 3

Three details of heapq save time in practice. It is a min-heap only, so for a max-heap you push negated keys and negate again on the way out. heapq.heapify(lst) converts an existing list in place in O(n), which is much cheaper than n pushes. And to queue items by priority you push tuples (priority, item) - but if two priorities tie, Python then compares the items themselves, which raises TypeError for objects that do not support comparison. The standard fix is a tiebreaker: push (priority, counter, item) with a monotonically increasing counter, which also makes the queue stable in arrival order.

Key idea: a priority queue serves by priority, not arrival order, and a heap is the standard efficient implementation; in Python remember it is min-only and add a counter to break priority ties.

Worked example: building a heap and draining it

Push 5, 3, 8, 1, 9, 2 into a min-heap, one at a time. Each push appends to the end and sifts up while the new value is smaller than its parent:

push 5   [5]                    no parent
push 3   [5, 3] -> parent of index 1 is 0: 5 > 3, swap
         [3, 5]
push 8   [3, 5, 8]              parent of index 2 is 0: 3 < 8, stop
push 1   [3, 5, 8, 1] -> parent of 3 is 1: 5 > 1, swap
         [3, 1, 8, 5] -> parent of 1 is 0: 3 > 1, swap
         [1, 3, 8, 5]
push 9   [1, 3, 8, 5, 9]        parent of 4 is 1: 3 < 9, stop
push 2   [1, 3, 8, 5, 9, 2] -> parent of 5 is 2: 8 > 2, swap
         [1, 3, 2, 5, 9, 8] -> parent of 2 is 0: 1 < 2, stop

FINAL    [1, 3, 2, 5, 9, 8]

Notice that pushing 1 travelled two levels while pushing 9 travelled none. The path length is bounded by the height, log2(n), which is where O(log n) comes from - and most pushes stop early, so the average is well under the bound.

Now extract the minimum twice. Each pop takes the root, moves the last element into the root to keep the shape complete, and sifts down by swapping with the smaller child:

POP 1:  move 8 to the root      [8, 3, 2, 5, 9]
        children of 0: 3 and 2; smaller is 2; 8 > 2, swap
                                [2, 3, 8, 5, 9]
        index 2 has no children -> done.     returned 1

POP 2:  move 9 to the root      [9, 3, 8, 5]
        children of 0: 3 and 8; smaller is 3; 9 > 3, swap
                                [3, 9, 8, 5]
        children of 1: only 5;  9 > 5, swap
                                [3, 5, 8, 9]
        index 3 has no children -> done.     returned 2

Sifting down must compare against both children and swap with the smaller one. Swapping with the left child unconditionally is the classic heap bug: it can put a value above a smaller sibling and silently corrupt the invariant, with no error until a later pop returns the wrong element.

Key idea: push appends and sifts up, pop swaps the last element to the root and sifts down against the smaller child; both walk at most log2(n) levels.

Why building a heap costs O(n), not O(n log n)

Pushing n items one at a time costs n * O(log n) = O(n log n). But heapify does it in O(n), by sifting down from the last internal node backwards to the root. The counting argument is worth seeing because the result looks impossible:

Nodes at height h in a heap of n nodes:   at most  n / 2^(h+1)
Cost of sifting down from height h:       O(h)

total = sum over h of  (n / 2^(h+1)) * h
      = (n/2) * sum over h of  h / 2^h
      = (n/2) * 2                          since sum h/2^h converges to 2
      = O(n)

The intuition behind the algebra: half the nodes are leaves and sift down zero levels, a quarter sift down at most one, an eighth at most two. The many cheap nodes vastly outnumber the few expensive ones, and the series converges. This is why "build a heap, then pop everything" - heapsort - is O(n) + n*O(log n) = O(n log n), with the build phase effectively free.

Key idea: bottom-up heapify is O(n) because most nodes are near the bottom and sift down almost no distance; only repeated pushing costs O(n log n).

How the operations work and cost

To insert, place the new element at the end of the array and let it "bubble up," swapping with its parent while it is smaller (for a min-heap). To extract the root, move the last element to the root and let it "sink down," swapping with its smaller child until the heap property is restored. Both bubbling up and sinking down travel at most the height of the tree, which is log n, so both are O(log n). Peeking at the minimum is just reading the root, O(1).

Operation	Complexity
Peek min or max (root)	O(1)
Insert (push)	O(log n)
Extract min or max (pop)	O(log n)

Heaps power task schedulers, Dijkstra's shortest-path algorithm, and the heapsort algorithm (build a heap, then repeatedly extract the min for an O(n log n) sort). Space is O(n).

Heapsort deserves a note, because its profile is unusual. It is O(n log n) in the worst case, not just on average - the guarantee quicksort lacks - and it sorts in place with O(1) auxiliary space, which merge sort lacks. On paper it dominates both. In practice it is usually the slowest of the three, because sifting down jumps from index i to 2i+1, doubling the stride at every level and defeating the cache exactly as badly as quicksort's sequential scan pleases it. Heapsort's real role today is as the safety net inside introsort: quicksort runs until its recursion goes too deep, then heapsort takes over and guarantees the bound.

Compare the three ways to serve a priority queue. A sorted list gives O(1) extraction but O(n) insertion. An unsorted list gives O(1) insertion but O(n) extraction. A heap gives O(log n) for both, which is the right trade whenever inserts and extracts are interleaved. A balanced BST also gives O(log n) for both and additionally supports ordered iteration and arbitrary deletion - so use a tree when you need those, and a heap when you do not, because the heap's constant factors and memory footprint are far better.

Key idea: peek is O(1) and both insert and extract are O(log n) because they travel one tree height; heapsort is in-place and worst-case O(n log n) but cache-hostile, and a heap beats both list forms when inserts and extracts interleave.

Where people get stuck

• "A heap is fully sorted." It is only partially ordered. The root is the extreme, but siblings and deeper levels are not. Printing the array is not printing sorted output.
• "You can search a heap for any value quickly." No. Without full ordering, finding an arbitrary value is O(n); a heap is optimized for the min or max only.
• "A heap needs pointers like other trees." A complete binary heap lives in a plain array using index arithmetic, no pointers required.
• "A priority queue is just a normal queue." A normal queue serves oldest-first; a priority queue serves highest-priority-first.
• Sifting down against the left child only. You must compare both children and swap with the smaller (for a min-heap). Getting this wrong corrupts the heap silently - no exception, just wrong answers several pops later.
• Mutating an item already in the heap. Changing an object's priority in place does not re-sift it, so the invariant breaks. heapq has no decrease-key; the usual pattern is lazy deletion - push a new entry with the better priority and skip stale entries when they surface.
• Tuple comparison blowing up on a tie. (2, task_a) versus (2, task_b) makes Python compare the tasks. Add an incrementing counter as the second element.
• Using n pushes when heapify would do. Building from an existing list is O(n) with heapify and O(n log n) by pushing. On a million items that is a real difference.

Recap

• A min-heap keeps the smallest element at the root via the parent-child rule; a max-heap keeps the largest. It is partially ordered, which is precisely why it is cheap.
• A heap is a complete binary tree stored in an array: children of i are at 2i+1 and 2i+2, and the parent is at (i-1)//2.
• Push appends and sifts up; pop moves the last element to the root and sifts down against the smaller child. Both walk at most log2(n) levels.
• Peek is O(1), insert and extract are O(log n), and space is O(n).
• Bottom-up heapify builds a heap in O(n), because the node counts halve as the sift distance grows and the series sum h/2^h converges to 2.
• Heapsort is in-place and worst-case O(n log n) but cache-unfriendly; it serves mainly as the guaranteed fallback inside introsort.

Any time you catch yourself sorting a list only to take the first element, and then sorting again after a change, you wanted a heap.

Sources

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Heapsort: Maintaining the heap property, building a heap, and priority queues. In Introduction to algorithms (4th ed., ch. 6). MIT Press. find source ↗
2. Williams, J. W. J. (1964). Algorithm 232: Heapsort. Communications of the ACM, 7(6), 347-348. find source ↗
3. Sedgewick, R., & Wayne, K. (2011). Priority queues: Binary heaps and heapsort. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
4. Python Software Foundation. (n.d.). heapq - Heap queue algorithm. Python 3 documentation. docs.python.org
5. Morin, P. (2013). Heaps: Implicit binary trees and binary heaps. In Open data structures (ch. 10). opendatastructures.org
6. Demaine, E., Ku, J., & Solomon, J. (2020). Lecture 8: Binary heaps. 6.006 Introduction to Algorithms, MIT OpenCourseWare. ocw.mit.edu
7. Halim, S., Halim, F., & Koh, Z. C. (n.d.). Binary heap (priority queue). VisuAlgo, National University of Singapore. visualgo.net

The big picture

Every structure so far has been about storing things. A graph is about storing relationships - and once you can see a problem as a graph, a large library of solved algorithms becomes available to you at once. The hard part is usually not the algorithm; it is deciding what a vertex is and what an edge means.

The big picture

Graphs are the most general data structure for relationships, and they model an enormous range of real systems: road maps, social networks, the web, course prerequisites, and computer networks. Before you can run algorithms on a graph you must decide how to store it, and that choice trades memory against speed. This lesson sets up the vocabulary and the two standard representations you will use for the traversals in the next lesson.

What a graph is

A graph is a set of vertices (also called nodes) connected by edges (links between two vertices). Picture a map of cities (vertices) joined by roads (edges). Unlike a tree, a graph may contain cycles, may be disconnected into separate pieces, and places no limit on how vertices connect. Graphs model road maps, social networks, web pages and their links, prerequisites, and computer networks. Trees, in fact, are just a special case of graphs: a tree is a connected graph with no cycles.

Key idea: a graph is vertices joined by edges, more general than a tree because it allows cycles and disconnection.

Varieties of graph

• Undirected: edges have no direction; a friendship link goes both ways.
• Directed (digraph): edges point one way, like a one-way street or a "follows" relationship on social media.
• Weighted: each edge carries a number, such as a distance, cost, or travel time.
• Unweighted: edges simply exist or not, with no number attached.

Key idea: edges may be directed or undirected and weighted or unweighted, and those choices reflect the real relationship being modeled.

A handful of further terms will appear constantly from here on:

• Degree of a vertex is how many edges touch it. In a directed graph it splits into in-degree and out-degree. Every edge contributes to exactly two degrees, so the sum of all degrees equals 2E - the handshake lemma, and a quick way to check a graph you have just built.
• A path is a sequence of vertices each joined to the next; a cycle is a path that returns to its start.
• A connected component is a maximal set of vertices all reachable from each other. A graph with two components is two separate islands, and any traversal started in one will never see the other.
• A DAG is a directed acyclic graph - directed edges, no cycles. Build dependencies, course prerequisites, and spreadsheet formulas are all DAGs, and their acyclicity is what makes a valid ordering possible.
• A simple graph has no self-loops and no repeated edges. Real data often violates both, so decide explicitly whether your model permits them.

Density is the quantity that drives the storage decision. An undirected simple graph on V vertices has at most V(V-1)/2 edges. A graph near that limit is dense; one with only a few edges per vertex is sparse. Almost every real network is sparse: your social graph has a few hundred connections, not eight billion.

Two ways to store a graph

The representation you choose affects both memory and speed. The two standard choices are the adjacency list and the adjacency matrix. Let V be the number of vertices and E the number of edges.

An adjacency list stores, for each vertex, a list of its neighbors, like each city keeping a short list of the cities it has a direct road to. It uses O(V + E) space, which is efficient for sparse graphs (graphs with relatively few edges), the common real-world case.

# Adjacency list as a dict of neighbor lists
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"]
}
print(graph["A"])   # neighbors of A: ['B', 'C']

An adjacency matrix is a V by V grid where cell [i][j] is 1 (or the edge weight) if an edge runs from vertex i to vertex j, and 0 otherwise. It is like a full mileage chart between every pair of cities. Checking whether two specific vertices are connected is O(1), but it always uses O(V squared) space regardless of how few edges exist, which is wasteful for sparse graphs.

Representation	Space	Check edge (u,v)	Best for
Adjacency list	O(V + E)	O(degree of u)	Sparse graphs
Adjacency matrix	O(V^2)	O(1)	Dense graphs

Most practical graphs are sparse, so the adjacency list is the usual default, and it is what the traversal algorithms in the next lesson assume.

Key idea: an adjacency list uses O(V plus E) space and suits sparse graphs; an adjacency matrix uses O(V squared) but checks any edge in O(1), suiting dense graphs.

Worked example: one graph, three representations

Here is the six-vertex undirected graph we will traverse in the next lesson. Seven edges: A-B, A-C, B-D, C-D, C-E, D-F, E-F.

          A
         / \
        B   C
         \ / \
          D   E
           \ /
            F

edges: A-B, A-C, B-D, C-D, C-E, D-F, E-F

As an adjacency list, with each vertex's neighbours in alphabetical order:

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D", "E"],
    "D": ["B", "C", "F"],
    "E": ["C", "F"],
    "F": ["D", "E"],
}

Check it with the handshake lemma: the degrees are 2, 2, 3, 3, 2, 2, summing to 14, which is 2 * 7 edges. Correct. If that sum comes out odd, you have forgotten to add an edge in one direction.

The same graph as an adjacency matrix, rows and columns in order A through F:

     A  B  C  D  E  F
  A  0  1  1  0  0  0
  B  1  0  0  1  0  0
  C  1  0  0  1  1  0
  D  0  1  1  0  0  1
  E  0  0  1  0  0  1
  F  0  0  0  1  1  0

Two properties are visible at a glance. The matrix is symmetric across the diagonal, because the graph is undirected - for a directed graph it would not be. And the diagonal is all zeros, because there are no self-loops. Each row sums to that vertex's degree.

There is a third representation, the edge list: just the pairs, [("A","B"), ("A","C"), ("B","D"), ...]. It uses O(E) space, it is the natural format for files and network transfer, and it is what algorithms that process edges in sorted order want - Kruskal's minimum spanning tree, for instance. Its weakness is that finding one vertex's neighbours requires scanning every edge, which is O(E). Most programs read an edge list and immediately build an adjacency list from it.

Now the memory arithmetic that decides the choice, for a realistic sparse graph with V = 10,000 and E = 50,000:

adjacency matrix:  V^2 = 100,000,000 cells
                   at 1 byte each  -> about 100 MB
                   as Python objects (8 bytes) -> about 800 MB

adjacency list:    V + 2E = 10,000 + 100,000 = 110,000 entries
                   at 8 bytes each -> under 1 MB

density = 2E / (V * (V-1)) = 100,000 / 99,990,000 = about 0.1%

A factor of roughly a thousand, and 99.9 percent of the matrix would be zeros. The matrix only earns its keep when the graph is genuinely dense, when you need O(1) edge tests in a tight loop, or when you want to use matrix algebra - raising an adjacency matrix to the k-th power counts paths of length k, which is elegant and occasionally exactly what you need.

Key idea: pick the representation from the density and the operations you will perform: adjacency list for sparse graphs and neighbour iteration, matrix for dense graphs and O(1) edge tests, edge list for storage and edge-ordered algorithms.

Cost of the common operations

OPERATION                   ADJ. LIST          ADJ. MATRIX
add an edge                 O(1)               O(1)
check if edge (u,v) exists  O(degree of u)     O(1)
remove an edge              O(degree of u)     O(1)
iterate u's neighbours      O(degree of u)     O(V)
iterate all edges           O(V + E)           O(V^2)
space                       O(V + E)           O(V^2)

The row that decides most real cases is "iterate u's neighbours". BFS, DFS, Dijkstra, and topological sort all do exactly that, once per vertex, and nothing else. On an adjacency list the total across the whole traversal is the sum of all degrees, which is 2E, giving the O(V + E) that every graph algorithm in this course quotes. On a matrix the same traversal costs O(V) per vertex whether or not the neighbours exist, so it becomes O(V^2) - which on our 10,000-vertex graph is a hundred million steps instead of a hundred and ten thousand.

Key idea: the O(V + E) bound in every traversal comes directly from adjacency-list neighbour iteration summing to 2E; on a matrix the same algorithms degrade to O(V^2).

Where people get stuck

• "Graphs are the same as trees." A tree is a special graph: connected and acyclic with exactly V - 1 edges. General graphs allow cycles and disconnected pieces.
• "The adjacency matrix is always better because edge checks are O(1)." It costs O(V^2) memory even for sparse graphs, and makes neighbour iteration O(V). The list is the default for a reason.
• "An adjacency list wastes memory on missing edges." It stores only the edges that exist, giving O(V + E).
• "All edges are two-way." Only undirected edges are. In an undirected adjacency list you must append in both directions - adding only graph[u].append(v) creates a graph where the edge exists from one side and not the other, and traversals then produce answers that are wrong but not obviously wrong.
• Isolated vertices vanishing. Building a dict of lists from an edge list only creates keys for vertices that appear in an edge. A vertex with no edges is silently missing, so any count of vertices or components comes out short. Initialize every known vertex first.
• defaultdict creating phantom vertices. With defaultdict(list), merely reading graph[x] for an unknown x inserts an empty entry. Check membership with in before indexing, or use graph.get(x, []).
• Ignoring self-loops and parallel edges. Real data has them - a road that loops back, two flights between the same cities. Decide whether to keep, merge, or drop them before the algorithm meets them.

Recap

• A graph is vertices connected by edges; it may have cycles and be disconnected, unlike a tree.
• Edges can be directed or undirected and weighted or unweighted; the sum of all degrees equals 2E, which is a cheap correctness check.
• An undirected simple graph has at most V(V-1)/2 edges; almost all real graphs are far below that and count as sparse.
• An adjacency list uses O(V + E) space and fits sparse graphs, the usual default; the matrix of an undirected graph is symmetric with a zero diagonal.
• An adjacency matrix uses O(V^2) space but checks any edge in O(1); an edge list uses O(E) and suits files and edge-ordered algorithms.
• Neighbour iteration over an adjacency list sums to 2E across a traversal, which is where the O(V + E) bound of BFS and DFS comes from.

Choose the representation before you choose the algorithm. Nearly every graph algorithm you meet from here assumes an adjacency list, and quotes a complexity that is only true if you supplied one.

Sources

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Elementary graph algorithms: Representations of graphs. In Introduction to algorithms (4th ed., ch. 20). MIT Press. find source ↗
2. Sedgewick, R., & Wayne, K. (2011). Undirected graphs: Glossary and adjacency-lists representation. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
3. Sedgewick, R., & Wayne, K. (2011). Directed graphs: Digraph representations and DAGs. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
4. Morin, P. (2013). Graphs: AdjacencyMatrix and AdjacencyLists. In Open data structures (ch. 12). opendatastructures.org
5. Halim, S., Halim, F., & Koh, Z. C. (n.d.). Graph data structures: Adjacency matrix, adjacency list, edge list. VisuAlgo, National University of Singapore. visualgo.net
6. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269-271. link.springer.com
7. Demaine, E., Ku, J., & Solomon, J. (2020). Lecture 9: Breadth-first search: Graph representations. 6.006 Introduction to Algorithms, MIT OpenCourseWare. ocw.mit.edu

The big picture

BFS and DFS are the same algorithm. Take the frontier of discovered-but-unexplored vertices, remove one, look at its neighbours, add the new ones. The only difference is whether the frontier is a queue or a stack - and from that one choice follow shortest paths on one side and cycle detection and topological sorting on the other.

The big picture

Building a graph is only useful if you can explore it. Breadth-first search and depth-first search are the two fundamental ways to visit a graph, and nearly every graph algorithm, from finding shortest routes to detecting cycles to scheduling tasks, is built on one of them. They differ in the order they visit vertices, and that difference decides which problems each one solves best.

This lesson implements both, explains why BFS finds shortest paths in unweighted graphs, and states their shared O(V plus E) cost.

Traversing a graph

Once a graph is built, the fundamental task is to traverse it: systematically visit the vertices reachable from a chosen start. The two core strategies are breadth-first search and depth-first search. Both visit every reachable vertex and every edge once, so both run in O(V + E) time with an adjacency list. The crucial detail in a graph, unlike a tree, is that cycles can exist, so you must track a visited set of already-seen vertices to avoid looping forever. Without it, a cycle would send the traversal around in circles endlessly.

Key idea: graph traversal visits reachable vertices systematically in O(V plus E), and a visited set is required to avoid infinite loops on cycles.

Breadth-first search (BFS)

BFS explores in expanding rings: it visits the start, then all of its neighbors, then all of their unvisited neighbors, and so on. It uses a queue (first in, first out), which is what produces the ring-by-ring order. Think of dropping a stone in a pond: the ripples reach nearby points before farther ones. Because it fans out level by level, BFS discovers vertices in order of their distance from the start, which is why BFS finds the shortest path in an unweighted graph, meaning the path with the fewest edges.

from collections import deque

def bfs(graph, start):
    visited = set([start])
    q = deque([start])
    order = []
    while q:
        node = q.popleft()     # dequeue (FIFO)
        order.append(node)
        for nbr in graph[node]:
            if nbr not in visited:
                visited.add(nbr)
                q.append(nbr)
    return order

Key idea: BFS uses a queue to explore ring by ring, so it reaches every vertex by a fewest-edges path, giving shortest paths in unweighted graphs.

Worked example: BFS on the six-vertex graph

Use the graph from the previous lesson, with neighbours listed alphabetically:

A: B, C     B: A, D     C: A, D, E
D: B, C, F  E: C, F     F: D, E

Start at A. Track the queue, the visited set, and the distance recorded when each vertex is first discovered:

step  dequeue  neighbours checked      newly visited   queue after    order
 0      -           -                  A (dist 0)      [A]            -
 1      A       B new, C new           B(1), C(1)      [B, C]         A
 2      B       A seen, D new          D(2)            [C, D]         A B
 3      C       A seen, D seen, E new  E(2)            [D, E]         A B C
 4      D       B seen, C seen, F new  F(3)            [E, F]         A B C D
 5      E       C seen, F seen         -               [F]            A B C D E
 6      F       D seen, E seen         -               []             A B C D E F

FINAL ORDER:     A  B  C  D  E  F
FINAL DISTANCES: A=0  B=1  C=1  D=2  E=2  F=3

Verify a distance by hand. F is reached in 3 edges by A-B-D-F and also by A-C-E-F, and no shorter route exists, so 3 is correct. Notice that the queue never held more than two distinct distances at once - first only 1s, then 1s and 2s, then 2s and 3s. That is the invariant that makes BFS correct: vertices leave the queue in nondecreasing order of distance, so the first time you reach a vertex you have reached it by a fewest-edges path. There is no need to revisit and improve, which is exactly why BFS is O(V + E) and Dijkstra, which must allow improvements, needs a priority queue.

To recover the path and not just the distance, record a parent when you first discover a vertex, then walk the parents backwards:

def bfs_paths(graph, start):
    parent = {start: None}
    q = deque([start])
    while q:
        node = q.popleft()
        for nbr in graph[node]:
            if nbr not in parent:          # 'in parent' doubles as 'visited'
                parent[nbr] = node
                q.append(nbr)
    return parent

def path_to(parent, target):
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]                      # reverse: start -> target

On our trace the parents are B from A, C from A, D from B, E from C, and F from D, so path_to(parent, "F") gives A, B, D, F - three edges, matching the computed distance. Had C been dequeued before B, the answer would have been A, C, E, F: equally short, and equally correct. Shortest paths are not unique.

Key idea: BFS dequeues vertices in nondecreasing distance order, so the first discovery of a vertex is already optimal; store a parent per vertex to rebuild the path itself.

Depth-first search (DFS)

DFS plunges as deep as possible along one path before backtracking, like exploring a maze by always taking a corridor to its end before returning to try another. It uses a stack (last in, first out), either explicitly or through the recursion call stack. DFS is the natural choice for detecting cycles, finding connected components (groups of mutually reachable vertices), topological sorting, and exploring mazes.

def dfs(graph, node, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(node)
    order.append(node)
    for nbr in graph[node]:
        if nbr not in visited:
            dfs(graph, nbr, visited, order)   # recurse deeper
    return order

Trace it on the same graph from A, taking neighbours in alphabetical order:

visit A         neighbours B, C     -> descend into B
  visit B       A seen, D new       -> descend into D
    visit D     B seen, C new       -> descend into C
      visit C   A seen, D seen, E   -> descend into E
        visit E C seen, F new       -> descend into F
          visit F   D seen, E seen  -> return
        return E
      return C
    back in D: F already seen       -> return
  return B
back in A: C already seen           -> return

ORDER: A  B  D  C  E  F

Compare that with BFS's A B C D E F. DFS reached F at depth 5 through A-B-D-C-E-F, a five-edge walk, while BFS found F at distance 3. DFS visits every vertex, but the order it finds them says nothing about distance - which is precisely why it cannot be used for shortest paths.

The iterative form makes the stack explicit and avoids Python's recursion limit on long paths:

def dfs_iter(graph, start):
    visited, stack, order = set(), [start], []
    while stack:
        node = stack.pop()                 # LIFO - the only change from BFS
        if node in visited:
            continue                       # a vertex can be stacked twice
        visited.add(node)
        order.append(node)
        for nbr in reversed(graph[node]):  # reversed keeps alphabetical order
            if nbr not in visited:
                stack.append(nbr)
    return order

Two details differ from the recursive version. The reversed call is needed because a stack returns the last item pushed, so pushing B then C would explore C first; reversing restores the recursive order. And a vertex can be pushed more than once before it is popped, so the visited check has to happen at pop time as well - which is why the queue-based BFS above marks vertices on discovery instead.

Key idea: DFS uses a stack or recursion to dive deep before backtracking, which suits cycle detection, connected components, and topological sorting - and its visit order carries no distance information.

What each traversal is really for

Both traversals are frameworks rather than finished algorithms. Four standard specializations cover most uses:

• Connected components. Loop over every vertex; if it is unvisited, run a traversal from it and label everything found with the same component id. Total cost stays O(V + E) because each vertex and edge is touched once overall. This is also the answer to "my traversal missed half the graph" - a single traversal only reaches one component.
• Cycle detection, undirected. During DFS, a neighbour that is already visited and is not the vertex you came from closes a cycle. The parent exclusion matters: without it every single edge looks like a cycle, because you can always step back where you came from.
• Cycle detection, directed. Two states are not enough. Track three: unvisited, in-progress (currently on the recursion stack), and finished. An edge into an in-progress vertex is a back edge and proves a cycle; an edge into a finished vertex is harmless. Using plain "visited" here reports cycles in perfectly acyclic diamond-shaped graphs, and it is the most common graph bug there is.
• Topological sort. On a DAG, run DFS and prepend each vertex to a list as it finishes. The result orders every task after its prerequisites. If the same run detects a back edge, no valid order exists - the dependencies are circular.

BFS specializes differently: shortest paths and distances in unweighted graphs, testing whether a graph is bipartite by two-colouring alternate levels, and finding the nearest match when solutions may be shallow. Web crawlers and network flood-fills use BFS for the same reason - you want the near things first.

Key idea: wrap a traversal in an outer loop over all vertices for components; use three states rather than two to detect cycles in a directed graph; and DFS finish order reversed is a topological sort.

Choosing between them

	BFS	DFS
Data structure	Queue (FIFO)	Stack or recursion (LIFO)
Order	By distance from start	Deep along a path first
Shortest path (unweighted)?	Yes	Not guaranteed
Time	O(V + E)	O(V + E)

Both use O(V) extra space for the visited set (plus the queue or recursion stack). The rule of thumb: use BFS when you need the shortest path in an unweighted graph or want to search nearest-first; use DFS when you need to exhaustively explore, detect cycles, or the solution is likely deep. For weighted shortest paths you would move on to Dijkstra's algorithm, which uses the priority queue you met in the previous module.

Where does the O(V + E) come from? Each vertex is enqueued or pushed at most once, contributing V. For each vertex dequeued, the algorithm iterates that vertex's neighbour list, and summed across all vertices those lists contain 2E entries in an undirected graph, contributing E. Add them and the traversal is O(V + E) - but only with an adjacency list. Hand the same code an adjacency matrix and the neighbour scan becomes O(V) per vertex, making the whole traversal O(V^2).

The space bounds deserve a similar honesty. Both need O(V) for the visited set. Beyond that, BFS's queue holds an entire frontier, which on a wide graph approaches V; DFS's stack holds one vertex per level of the current path, which is the length of the longest path. On a broad shallow graph DFS uses far less memory; on a long thin one, BFS does. Neither is universally lighter.

Key idea: both are O(V + E) time with an adjacency list and O(V) space; choose BFS for shortest unweighted paths and DFS for deep or exhaustive exploration, and check which frontier your graph's shape makes smaller.

Where people get stuck

• "DFS finds the shortest path too." Not in general. On our sample graph DFS reaches F after five edges when three suffice. Only BFS guarantees a fewest-edges path in an unweighted graph.
• "You do not need a visited set if the graph looks simple." Any cycle causes an infinite loop without one, and even without cycles you would revisit vertices exponentially often. It is always required.
• "BFS uses a stack and DFS uses a queue." It is the reverse: BFS uses a queue, DFS a stack or recursion.
• "BFS gives shortest paths even with edge weights." Plain BFS counts edges, not weights. Weighted shortest paths need Dijkstra's algorithm, which replaces the queue with a priority queue - the heap from Lesson 14.
• Marking visited at dequeue instead of at discovery. In BFS this lets the same vertex be enqueued once per incoming edge, so the queue swells to O(E) and work is repeated. Mark a vertex the moment you push it.
• Using a list as the BFS queue. q.pop(0) is O(n), turning an O(V + E) traversal into O(V^2 + VE). Use collections.deque.
• Assuming one traversal sees the whole graph. It only visits one connected component. To cover everything, loop over all vertices and start a fresh traversal from each unvisited one.
• Two-state cycle detection on a directed graph. A finished vertex reached a second time is not a cycle. You need the in-progress state, or you will report cycles in acyclic graphs.
• Recursive DFS on a long path. A chain of 5000 vertices overflows Python's frame limit. Use the iterative version when depth may be large.

Recap

• BFS and DFS are one algorithm with two frontiers: a queue gives BFS, a stack gives DFS.
• Both visit reachable vertices in O(V + E) with an adjacency list and need a visited set; on a matrix they degrade to O(V^2).
• BFS dequeues in nondecreasing distance order, so first discovery is optimal - that is why it finds shortest paths in unweighted graphs, and why a parent map rebuilds the path.
• On the sample graph, BFS visits A B C D E F with distances 0, 1, 1, 2, 2, 3, while DFS visits A B D C E F and reaches F the long way.
• DFS specializes into connected components, cycle detection, and topological sort; directed cycle detection needs three states, not two.
• Space is O(V) for both, but BFS holds a whole frontier while DFS holds one path, so the graph's shape decides which is lighter.

That closes the course. You now have the vocabulary to state what an algorithm costs, the structures to make those costs small, and the traversals that most of the remaining algorithmic world is built on. The next steps - Dijkstra, dynamic programming, minimum spanning trees - are all recombinations of what you have here.

Sources

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Elementary graph algorithms: Breadth-first search, depth-first search, and topological sort. In Introduction to algorithms (4th ed., ch. 20). MIT Press. find source ↗
2. Demaine, E., Ku, J., & Solomon, J. (2020). Lecture 9: Breadth-first search. 6.006 Introduction to Algorithms, MIT OpenCourseWare. ocw.mit.edu
3. Demaine, E., Ku, J., & Solomon, J. (2020). Lecture 10: Depth-first search. 6.006 Introduction to Algorithms, MIT OpenCourseWare. ocw.mit.edu
4. Sedgewick, R., & Wayne, K. (2011). Undirected graphs: Depth-first search and breadth-first search. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
5. cp-algorithms contributors. (n.d.). Breadth-first search. Algorithms for Competitive Programming. cp-algorithms.com
6. cp-algorithms contributors. (n.d.). Depth-first search: Edge classification and cycle detection. Algorithms for Competitive Programming. cp-algorithms.com
7. Halim, S., Halim, F., & Koh, Z. C. (n.d.). Graph traversal (depth/breadth first search). VisuAlgo, National University of Singapore. visualgo.net