Race modeTwo algorithms, the same array, side by side
compare ? swap ⇄ write read sorted
Draw walls · drag S and E
wall mud ×5 frontier visited path

Complexity reference

$n$ = number of items, $k$ = range of key values, $d$ = number of digits, $b$ = radix (10 here), $V$ and $E$ = vertices and edges of the graph. Space is auxiliary memory beyond the input.

What an algorithm costs

In one sentence: Big-O tells you how much more work an algorithm does when the input gets bigger. Double $n$ and an $O(n)$ algorithm does twice the work, an $O(n^2)$ one four times the work. That is why it matters more than the speed of your computer.

We measure an algorithm by how the number of primitive operations grows with the input size $n$, ignoring constant factors and lower-order terms. Formally, $f(n) = O(g(n))$ if there are constants $c>0$ and $n_0$ such that $f(n) \le c\,g(n)$ for all $n \ge n_0$. $\Omega$ gives a lower bound and $\Theta$ a tight bound (both $O$ and $\Omega$).

$$\begin{gathered}O(1) \subset O(\log n) \subset O(n) \subset O(n\log n)\\ \subset O(n^2) \subset O(2^n) \subset O(n!)\end{gathered}$$

The counters in the lab are the raw material of this analysis: comparisons (is $A[i] > A[j]$?), swaps, single writes, and array accesses (every read or write of the main array).

Quadratic sorts

Bubble sort repeatedly swaps adjacent out-of-order pairs; after pass $i$ the largest $i+1$ items are in their final places. Pass $i$ needs $n-1-i$ comparisons, so the worst case is

$$C_{\text{worst}} = \sum_{i=0}^{n-2} (n-1-i) = \frac{n(n-1)}{2} = \Theta(n^2).$$

With the early-exit flag a sorted array needs just one pass of $n-1$ comparisons. Insertion sort grows a sorted prefix, shifting larger elements one place right. It performs exactly one shift per inversion (a pair $i<j$ with $A[i]>A[j]$), so its cost is $\Theta(n + I)$ where $I$ is the number of inversions: excellent on nearly sorted data. Selection sort always makes $n(n-1)/2$ comparisons but at most $n-1$ swaps, useful when writes are expensive.

Divide and conquer

Merge sort splits the array in half, sorts each half recursively and merges them in linear time:

$$T(n) = 2\,T\!\left(\tfrac{n}{2}\right) + \Theta(n) \;\Rightarrow\; T(n) = \Theta(n \log n)$$

Intuitively: halving $n$ repeatedly reaches 1 after $\log_2 n$ levels of recursion, and each level does $\Theta(n)$ merging work in total, so the work is $n \times \log_2 n$. (Formally this is case 2 of the master theorem, a standard recipe for such recurrences: $a=2$, $b=2$, $f(n)=\Theta(n^{\log_b a})$.) Merging into an auxiliary array costs $O(n)$ extra space; taking from the left half on ties makes it stable.

Quicksort partitions around a pivot so that smaller items go left and larger go right, then recurses. If the pivot splits evenly, $T(n)=2T(n/2)+\Theta(n)=\Theta(n\log n)$; if it is always the minimum or maximum, $T(n)=T(n-1)+\Theta(n)=\Theta(n^2)$. The Lomuto scheme (pivot = last element) hits that worst case on already-sorted or reversed input. Hoare's scheme scans from both ends, uses about three times fewer swaps on average, and here takes the middle element as pivot, which avoids the sorted-input trap. Random pivots give expected $\approx 1.39\,n\log_2 n$ comparisons.

Heapsort builds a binary max-heap in $O(n)$ time (node $i$ has children $2i+1$ and $2i+2$), then repeatedly swaps the root to the end and sifts down: $\Theta(n\log n)$ in every case with $O(1)$ extra space, but not stable and cache-unfriendly.

The comparison lower bound and how to beat it

Any comparison sort is a binary decision tree with at least $n!$ leaves, so its height (worst-case comparisons) is at least

$$\log_2 n! = n\log_2 n - n\log_2 e + O(\log n) = \Omega(n \log n).$$

Counting sort and radix sort avoid comparisons by using the keys as array indices. Counting sort takes $\Theta(n+k)$ for integer keys in $[0,k]$. LSD radix sort runs a stable counting sort on each of $d$ digits in base $b$: $\Theta(d(n+b))$. Their counters show zero comparisons.

Searching

Linear search checks items one by one: $n$ comparisons in the worst case (target last or absent). Binary search on a sorted array halves the live interval $[lo, hi]$ at each probe of $mid = \lfloor (lo+hi)/2 \rfloor$, so the worst case is

$$C_{\text{binary}}(n) = \lfloor \log_2 n \rfloor + 1 .$$

For $n = 10^6$ that is 20 probes instead of a million.

Graph search on a grid

Each free cell is a vertex joined to its four neighbours. Entering a normal cell costs 1; entering mud costs 5. All the algorithms share one template: take a node from the frontier, mark it visited, push its unvisited neighbours. They differ only in which node they take next:

  • BFS: a FIFO queue. Finds the path with the fewest moves; ignores weights.
  • DFS: a LIFO stack. Complete on finite grids but paths can be very long.
  • Dijkstra: the node with the smallest path cost $g(n)$ so far (priority queue). Optimal for non-negative weights; $O((V+E)\log V)$ with a binary heap.
  • A*: smallest $f(n) = g(n) + h(n)$, where $h$ estimates the remaining cost.
  • Greedy best-first: smallest $h(n)$ only. Fast, but not optimal.
$$\begin{gathered}h_{\text{Manhattan}} = |x-x_e| + |y-y_e|\\ h_{\text{Euclid}} = \sqrt{(x-x_e)^2 + (y-y_e)^2}\end{gathered}$$

A* is guaranteed optimal when $h$ is admissible (never overestimates the true remaining cost). Both heuristics are admissible on a 4-connected grid with step cost $\ge 1$; Manhattan is tighter, so A* expands fewer nodes. Weighting it, $f = g + w\,h$ with $w>1$, trades optimality for speed: the cost found is at most $w$ times the optimum.

Simplifications: the grid is 4-connected, costs are attached to the cell being entered, and ties in priority queues are broken by smaller $h$ then insertion order. Real libraries differ in these details, which changes the exact counts but not the complexity.

1. Bubble sort on 5 numbers

Sort $[5, 1, 4, 2, 8]$ ascending.

  1. Pass 1: compare (5,1) swap → [1,5,4,2,8]; (5,4) swap → [1,4,5,2,8]; (5,2) swap → [1,4,2,5,8]; (5,8) no swap. 4 comparisons, 3 swaps. 8 is now final.
  2. Pass 2: (1,4) –; (4,2) swap → [1,2,4,5,8]; (4,5) –. 3 comparisons, 1 swap.
  3. Pass 3: (1,2) –; (2,4) –. 2 comparisons, 0 swaps, so the early-exit flag stops the sort.

Total: $4+3+2 = 9$ comparisons and 4 swaps. The 4 swaps equal the number of inversions: (5,1), (5,4), (5,2), (4,2).

2. Worst case in the lab

Set n = 48, order Reversed, algorithm Bubble sort. Every pair is an inversion, so

$$C = S = \frac{48 \times 47}{2} = 1128 .$$

The counters finish at 1128 comparisons and 1128 swaps, which is 2256 array writes (every swap writes two cells). Each swap reads and writes two cells and each comparison reads two, so accesses $= 2(1128) + 4(1128) = 6768$. Switch to Insertion sort: 1128 comparisons again, but now 1128 shifts plus 47 key placements $= 1175$ writes.

3. Why $n\log n$ wins

A laptop does roughly $10^9$ simple operations per second. Sorting $n = 10^6$ records (say, every payment a large mobile-money network handles in an hour):

  • $n^2/2 = 5\times10^{11}$ operations ≈ 500 s, over 8 minutes.
  • $n\log_2 n \approx 10^6 \times 19.93 \approx 2\times10^{7}$ operations ≈ 0.02 s.

The ratio is $n/(2\log_2 n) \approx 25\,000$. No hardware upgrade closes a gap like that.

4. Binary search step by step

Find 61 in $A = [3, 8, 14, 21, 29, 33, 40, 47, 52, 61, 66, 75, 81, 90, 97]$ ($n=15$, indices 0–14).

  1. $lo=0, hi=14, mid=7$: $A[7]=47 < 61$ → $lo=8$.
  2. $lo=8, hi=14, mid=11$: $A[11]=75 > 61$ → $hi=10$.
  3. $lo=8, hi=10, mid=9$: $A[9]=61$ → found in 3 probes.

Worst case $\lfloor\log_2 15\rfloor + 1 = 4$ probes; linear search needed 10 comparisons here.

5. Dijkstra versus BFS with mud

Start and end are 6 cells apart along a straight row of open cells, with open ground beside it. One cell in the middle of the row is mud. A detour around the mud takes 8 moves on normal ground.

  • BFS counts moves only: it takes the straight route, 6 moves, cost $5\cdot1 + 1\cdot5 = 10$.
  • Dijkstra compares costs: detour $= 8 < 10$, so it walks 8 moves at cost 8.

Try it in the lab: the optimality line under the results reports whether the path found matches Dijkstra's optimum.

6. One A* expansion

Start $(2,2)$, end $(9,5)$, Manhattan heuristic. The neighbour $(3,2)$ has $g = 1$ and $h = |3-9| + |2-5| = 9$, so $f = 10$. The neighbour $(1,2)$ has $g=1$, $h=11$, $f=12$. A* expands $(3,2)$ first, pulling the search towards the goal. Dijkstra treats both equally ($g=1$), which is why its visited region is a diamond while A*'s is a narrow beam.

Each challenge is checked automatically when the relevant run finishes. The light turns green when you succeed.

    Further experiments

    1. Sort the same random array of 100 items with every algorithm. Rank them by comparisons, then by writes. Is the ranking the same?
    2. Switch to Few unique and race Lomuto quicksort against Hoare quicksort. Why does Lomuto degrade when many keys are equal?
    3. In Big-O, use Run measurement with reversed input. Which curve does insertion sort follow now, and why does heapsort barely change?
    4. Build a long wall with one gap far from the straight line between S and E. Compare the nodes visited by greedy best-first and A*.
    5. Set the A* weight to 3 on a mud field. How much faster is it, and how far from optimal is the cost?
    Stable sort
    Equal keys keep their original relative order. Needed when sorting by several keys in turn (e.g. by surname, then by county).
    In-place
    Uses $O(1)$ (or $O(\log n)$ stack) extra memory beyond the input array.
    Inversion
    A pair of positions $i<j$ with $A[i]>A[j]$. A reversed array has $n(n-1)/2$ of them.
    Pivot
    The element quicksort partitions around.
    Heap
    A complete binary tree stored in an array where every parent is at least as large as its children (max-heap).
    Frontier (open set)
    Discovered nodes that have not yet been expanded.
    Admissible heuristic
    Never overestimates the true remaining cost; guarantees A* optimality.
    Consistent heuristic
    $h(u) \le c(u,v) + h(v)$ for every edge; implies admissible and means no node is expanded twice.
    Amortised / average case
    Average case averages over inputs; amortised averages over a sequence of operations on one structure.