← MA0 2 · Introduction to Algorithms and Numerical Analysis

Lesson 5

Trees, Searching and Sorting

Taught 24 Sept 2026

Connectivity and Trees

Connectivity

An undirected graph is connected if every vertex is reachable from every other vertex. By the proposition on walks and simple paths, equivalently, every pair of distinct vertices is joined by a simple path.

Figure 5.1. A graph with two components,

\{a, b, c, d\}

and

\{e, f, g\}

. The accented edge

\{e, f\}

is a bridge.

The graph of Figure 5.1 is disconnected: no path leads from $a$ to $e$ . Its vertices split into $\{a, b, c, d\}$ and $\{e, f, g\}$ .

Definition 5.2 (Connected component).

A connected component is a maximal connected induced subgraph: no further vertex of the graph can be included while keeping it connected. A graph is connected exactly when it has one component, and an isolated vertex forms a component by itself.

Theorem 5.3 (Edges of a connected graph).

A connected simple undirected graph with $n \geqslant 1$ vertices and $m$ edges has $m \geqslant n - 1$ .

Discussion.

The first proof grows the graph from one vertex. At each stage connectivity supplies an edge leaving the part reached so far, and that edge brings in exactly one new vertex, so reaching all $n$ vertices uses $n - 1$ distinct edges of the graph.

The second proof is an induction on $n$ that removes a vertex of smallest degree $k$ . If $k \geqslant 2$ , counting edge-ends gives $m \geqslant n$ directly and no induction is needed. If $k = 1$ , removing a vertex of degree one loses exactly one edge, and what is left is still connected, because a vertex of degree one cannot lie in the middle of a path. The hypothesis then applies to the smaller graph. The hypothesis has to be stated for every connected graph on $n - 1$ vertices, since it is applied to a graph that the proof constructs.

Proof.

Choose one vertex and mark it reached. If fewer than $n$ vertices are reached, connectivity guarantees an edge from some reached vertex to an unreached one; otherwise no path could lead out of the reached set. Mark that new vertex and keep the connecting edge. Each step reaches exactly one new vertex and keeps an edge not kept before. After $n - 1$ steps all $n$ vertices are reached, and we have found $n - 1$ distinct edges of $G$ . Therefore $m \geqslant n - 1$ .

A second proof, by induction, removes a vertex at each step.

Proof.

For each integer $n \geqslant 1$ , let $P(n)$ be the statement: every connected simple undirected graph with $n$ vertices has at least $n - 1$ edges.

Base case, $P(1)$ . A simple graph with one vertex has no pair of distinct vertices to join, so it has $m = 0$ edges. It is connected, and $0 = 1 - 1$ .

Step. Fix $n \geqslant 2$ and assume $P(n-1)$ . Take an arbitrary connected simple graph $G = (S, A)$ with $|S| = n$ and $|A| = m$ , and let $k = \min_{v \in S} d(v)$ be its smallest degree. Because $n \geqslant 2$ , a vertex of degree zero would have no path to any other vertex, contradicting connectivity, so $k \geqslant 1$ . Either $k = 1$ or $k \geqslant 2$ .

Case $k \geqslant 2$ . Every one of the $n$ vertices has degree at least $2$ , so $\sum_{v \in S} d(v) \geqslant 2n$ . Counting edge-ends gives $\sum_{v \in S} d(v) = 2m$ . Therefore $2m \geqslant 2n$ , so $m \geqslant n \geqslant n - 1$ . This case needs neither the removal of a vertex nor $P(n-1)$ .

Case $k = 1$ . Some vertex $v$ has exactly one edge, say $\{v, w\}$ . Remove $v$ and that edge, and call the result $G'$ . No other edge is removed, because no other edge touches $v$ , so $G'$ has $n - 1$ vertices and $m - 1$ edges.

Before applying $P(n-1)$ we check that $G'$ is connected. Take distinct vertices $a, b$ of $G'$ . Since $G$ is connected, a simple path joins $a$ to $b$ in $G$ . Neither endpoint is $v$ , because $a$ and $b$ remain. Nor can $v$ be an internal vertex of the path: the path would have to enter $v$ along one edge and leave along a second, distinct edge, and $v$ has only the edge $\{v, w\}$ . So the path uses neither $v$ nor its edge, and it is a path in $G'$ . This holds for every pair $a, b$ , so $G'$ is connected; when $n = 2$ , $G'$ has a single vertex and is connected by definition.

Now $G'$ satisfies the hypotheses of $P(n-1)$ : it is simple, connected, and has $n - 1$ vertices. Hence $m - 1 \geqslant (n - 1) - 1 = n - 2$ , and adding $1$ to both sides gives $m \geqslant n - 1$ . Both cases prove $P(n)$ from $P(n-1)$ , and with $P(1)$ induction proves the theorem for every $n \geqslant 1$ .

A connected graph with five vertices needs at least four edges, and a path through all five vertices attains the bound. Adding one edge to that path gives five edges and creates a cycle; the theorem does not claim that every connected graph has exactly $n - 1$ edges.

Definition 5.4 (Articulation vertex, bridge and vertex cut).

An articulation vertex is a vertex whose deletion, together with its edges, increases the number of connected components. A bridge, also called an isthmus, is an edge whose deletion increases that number. A vertex cut of a connected graph is a set of vertices whose deletion disconnects it, provided at least two vertices remain afterwards.

In Figure 5.1, the edge $\{e, f\}$ is a bridge: deleting it separates $e$ from $f$ and $g$ . The vertex $f$ is an articulation vertex: deleting it leaves $e$ and $g$ in separate components. All three edges of the left component are bridges too, since that component is a path through four vertices.

Strong Connectivity

For a directed graph, weak connectivity means connectivity once the directions of the arcs are ignored. Requiring directed routes both ways is a stronger condition.

Definition 5.5 (Strong connectivity and the reduced graph).

A directed graph is strongly connected if for every $u, v$ there is a directed walk from $u$ to $v$ and one from $v$ to $u$ . A strongly connected component is a maximal strongly connected induced subgraph. The reduced graph, or condensation, has one vertex for each strongly connected component, and an arc $C \to D$ whenever $C \neq D$ and some arc of the original graph goes from a vertex of $C$ to a vertex of $D$ .

Figure 5.2. The left graph is strongly connected. In the right graph no arc returns towards

d

or leaves

c

, and each vertex is a strongly connected component by itself.

In Figure 5.2, the left graph is strongly connected. In the right one every arc points away from $d$ and towards $c$ , so each of its four vertices is a strongly connected component by itself.

Figure 5.3. A directed graph whose strongly connected components are

\{a, b, c, d\}

and

\{e, f, g\}

, and its reduced graph. The accented arcs are the ones crossing between components.

In Figure 5.3, $\{a, b, c, d\}$ and $\{e, f, g\}$ are each strongly connected, and the only arcs between them point from the first set to the second. The reduced graph has two vertices $C_1, C_2$ and one arc $C_1 \to C_2$ . There cannot be an arc back: that would give reachability both ways and merge the two into one component.

Proposition 5.6 (The reduced graph has no directed cycle).

The reduced graph of any directed graph contains no simple directed cycle.

Discussion.

A cycle through several components would let every vertex in any one of them reach every vertex in the others and come back, so all of them would lie in a single strongly connected component. That contradicts maximality. The proof replaces each arc of the reduced graph by a walk in the original graph.

Proof.

The reduced graph has no loops, since its arcs join distinct components. Suppose $C_1 \to C_2 \to \cdots \to C_k \to C_1$ were a simple directed cycle of it with $k \geqslant 2$ . Each arc $C_i \to C_{i+1}$ comes from an arc of the original graph from some vertex of $C_i$ to some vertex of $C_{i+1}$ , and within each component any two vertices are joined by walks both ways. Concatenating, any vertex of $C_1$ can reach any vertex of $C_2$ , and any vertex of $C_2$ can reach any vertex of $C_1$ around the rest of the cycle. So $C_1 \cup C_2$ induces a strongly connected subgraph larger than $C_1$ , contradicting the maximality of $C_1$ .

Problem 5.1.

Show that a simple undirected graph on $n$ vertices with more than $\binom{n-1}{2}$ edges is connected, and give a disconnected graph with exactly $\binom{n-1}{2}$ edges.

Problem 5.2.

Find the strongly connected components and the reduced graph of the graph in Figure 4.8 of Lesson 4.

Trees

Definition 5.7 (Tree and forest).

A tree is a connected acyclic undirected graph. A forest is an undirected graph whose components are trees.

Figure 5.4. A tree on seven vertices (left), and the out-arborescence obtained by orienting its edges away from

a

(right).

The tree on the left of Figure 5.4 has seven vertices and six edges.

Proposition 5.8 (Counting the edges of a forest).

An acyclic undirected graph with $n$ vertices, $m$ edges and $c$ components satisfies $n = m + c$ .

Discussion.

The proof is an induction on the number of edges, and the step removes one. In an acyclic graph every edge is a bridge: if its endpoints were still joined after deleting it, that route together with the edge would be a cycle. So deleting an edge lowers $m$ by one and raises $c$ by one, and $m + c$ is unchanged. The base case, a graph with no edges, has every vertex as its own component.

Proof.

For $m = 0$ every vertex is its own component, so $c = n$ and $n = m + c$ . Assume the formula for all acyclic graphs with $m - 1$ edges, and take one with $m > 0$ edges. Delete one edge. Its endpoints cannot remain joined by another path, or that path together with the deleted edge would be a cycle. Hence the component containing the edge splits in two and the number of components rises from $c$ to $c + 1$ . The remaining graph is acyclic with $m - 1$ edges, so the hypothesis gives $n = (m - 1) + (c + 1) = m + c$ .

In particular a forest with $n$ vertices and $c$ components has $n - c$ edges.

Theorem 5.9 (Six characterisations of a tree).

Let $G$ be a finite simple undirected graph with $n \geqslant 1$ vertices. The following are equivalent.

$G$ is connected and acyclic.
$G$ is acyclic and has $n - 1$ edges.
$G$ is connected and has $n - 1$ edges.
$G$ is acyclic, and adding any missing edge creates exactly one simple cycle.
$G$ is connected, and deleting any edge disconnects it.
Every pair of distinct vertices is joined by exactly one simple path.

In particular each condition characterises a tree. For $K_1$ the clauses about adding or deleting an edge are vacuous.

Discussion.

Six conditions are proved equivalent by a cycle of implications, $1 \Rightarrow 6 \Rightarrow 5 \Rightarrow 4 \Rightarrow 2 \Rightarrow 3 \Rightarrow 1$ , so that each follows from each. The proof uses two facts. One is the relation between a cycle and two different paths between the same vertices: a cycle gives two routes around it, and two different paths give a cycle where they separate and rejoin. The other is the edge count $n = m + c$ for acyclic graphs, which converts between “has $n - 1$ edges” and “has one component”. The last implication, $3 \Rightarrow 1$ , uses the growing argument from the edge bound for connected graphs: it produces $n - 1$ edges forming a connected acyclic spanning subgraph, and a graph with only $n - 1$ edges has no others.

Proof.

$1 \Rightarrow 6$ . Connectivity supplies a simple path between every pair. If two different simple paths joined the same pair, follow them from the common start until they first diverge, and then along the first until it next meets the second; the two segments between those meeting points form a cycle. Thus the path is unique.

$6 \Rightarrow 5$ . $G$ is connected by 6. The unique simple path between the endpoints of an edge is that edge itself, so deleting it leaves the endpoints with no path between them.

$5 \Rightarrow 4$ . If $G$ had a cycle, deleting one of its edges would leave the endpoints of that edge connected along the rest of the cycle, so it would not disconnect $G$ . So $G$ is acyclic. By connectivity a simple path joins the endpoints of any missing edge, and adding the edge closes the path into a simple cycle. Now $G$ is connected and acyclic, so by $1 \Rightarrow 6$ that path is unique, and every simple cycle through the new edge consists of the new edge and a simple path of $G$ between its endpoints; so the new simple cycle is unique.

$4 \Rightarrow 2$ . If $G$ had two components, adding an edge between them would create no cycle, contrary to 4. Thus $c = 1$ , and since $G$ is acyclic the edge count $n = m + c$ gives $m = n - 1$ .

$2 \Rightarrow 3$ . Since $G$ is acyclic, the edge count gives $c = n - m = n - (n - 1) = 1$ . One component means that $G$ is connected.

$3 \Rightarrow 1$ . Because $G$ is connected, start at one vertex and repeatedly add an edge to a new vertex until every vertex is reached, as in the first proof of the edge bound. The chosen edges form a spanning subgraph with exactly $n - 1$ edges, one for each vertex other than the first. It is connected, since every vertex was joined to one reached earlier, and acyclic, since each edge was added to a new vertex and so cannot close a cycle among those already reached. Since $G$ itself has exactly $n - 1$ edges, it has no others, so $G$ is this subgraph and is acyclic.

In the tree of Figure 5.4 the unique path from $d$ to $f$ is $d, b, c, g, f$ , of length $4$ . Removing $\{b, c\}$ separates it into two components of sizes $3$ and $4$ . Adding the missing edge $\{d, g\}$ creates the unique cycle $d, b, c, g, d$ .

Rooted Trees

Definition 5.10 (Out-arborescence).

An out-arborescence rooted at $r$ is a directed graph in which there is exactly one directed simple path from $r$ to each vertex, and whose underlying undirected graph is a tree. Equivalently, $r$ has in-degree zero, every other vertex has in-degree one, and every vertex is reachable from $r$ . It has $n - 1$ arcs.

Orienting the tree of Figure 5.4 away from $a$ , as $a \to b$ , $b \to c$ , $b \to d$ , $c \to e$ , $c \to g$ and $g \to f$ , gives the out-arborescence with root $a$ on the right of the figure.

Definition 5.11 (Rooted and binary trees).

A rooted tree is a tree with one vertex $r$ chosen as its root. For a vertex $v \neq r$ , the vertex before $v$ on the unique path from $r$ to $v$ is the parent of $v$ , and $v$ is a child of its parent. A vertex with no children is a leaf, and the others are internal. The depth of $v$ is $d(r, v)$ , the length of the path from $r$ to $v$ , and the height of the tree is the largest depth of a vertex. The subtree at $v$ consists of $v$ and every vertex whose path from $r$ passes through $v$ , rooted at $v$ .

A binary tree is a rooted tree in which every vertex has at most two children, each labelled as a left child or a right child, with at most one of each. It is full if every internal vertex has exactly two children.

Orienting each edge of a rooted tree from parent to child gives an out-arborescence rooted at $r$ , since the unique path from $r$ to $v$ in the tree becomes the unique directed path. The subtrees at the children of the root of a binary tree are again binary trees, of height one less at most.

Proposition 5.12 (How large a binary tree of given height can be).

A binary tree of height at most $h$ has at most $2^h$ leaves and at most $2^{h+1} - 1$ vertices.

Discussion.

A binary tree consists of its root and at most two smaller binary trees below it, so both counts are proved by induction on the height. Each subtree at a child of the root has height at most $h - 1$ , so by induction each has at most $2^{h-1}$ leaves and $2^h - 1$ vertices, and there are at most two of them. The leaves of the whole tree are the leaves of the subtrees, unless the root has no children, and the vertices are those of the subtrees plus the root. The recurrence $T(h) = 2T(h-1) + 1$ with $T(0) = 1$ is the Tower of Hanoi recurrence shifted by one.

Proof.

We use induction on $h$ . A binary tree of height $0$ is a single vertex, which is a leaf: $1 = 2^0$ leaves and $1 = 2^1 - 1$ vertices.

Let $h \geqslant 1$ and suppose the claim holds for height at most $h - 1$ . If the root has no children the tree has one leaf and one vertex. Otherwise the root is not a leaf, and every other vertex lies in the subtree at exactly one of the at most two children of the root; each such subtree is a binary tree of height at most $h - 1$ . So there are at most $2 \cdot 2^{h-1} = 2^h$ leaves, and at most $1 + 2\,(2^h - 1) = 2^{h+1} - 1$ vertices.

Corollary 5.13 (Height of a binary tree).

A binary tree with $N$ vertices has height at least $\lceil \log_2 (N+1) \rceil - 1$ , and a binary tree with $K$ leaves has height at least $\lceil \log_2 K \rceil$ .

Proof.

If the height is $h$ , the proposition gives $N \leqslant 2^{h+1} - 1$ , so $h + 1 \geqslant \log_2(N + 1)$ , and since $h + 1$ is an integer, $h + 1 \geqslant \lceil \log_2(N+1) \rceil$ . Likewise $K \leqslant 2^h$ gives $h \geqslant \log_2 K$ , and so $h \geqslant \lceil \log_2 K \rceil$ .

Problem 5.3.

Show that every tree with at least two vertices has at least two leaves, that is, vertices of degree one, and that a full binary tree with $K$ leaves has exactly $K - 1$ internal vertices.

Problem 5.4.

Count the binary trees with $1$ , $2$ , $3$ and $4$ vertices, where two binary trees are the same only if they have the same shape including the left and right labels. Find a recurrence for the number with $N$ vertices by considering the sizes of the two subtrees at the root.

Searching

To search an array $T[0], \ldots, T[n-1]$ for a key $x$ is to return an index $i$ with $\operatorname{key}(T[i]) = x$ , or to report that there is none. This is the find(k) operation of the set interface on an array.

Linear Search

Linear search inspects the entries in order and returns the first index whose key equals $x$ . The entries need not be in any order.

Linear Search
Input:  an array T[0], …, T[n − 1] and a key x.
Output: an index i with key(T[i]) = x, or −1 if there is none.

    for i ≝ 0 to n − 1 do
        if key(T[i]) = x then return i
    return −1

def linear_search(T, x):
    for i in range(len(T)):
        if T[i] == x:
            return i
    return -1

T = [7, 3, 11, 2, 5]
print(linear_search(T, 2), linear_search(T, 4))   # 3 -1

The invariant before the pass for $i$ is that $x$ does not occur among $T[0], \ldots, T[i-1]$ . It holds trivially at $i = 0$ , a pass that does not return extends it by one position, and when the loop ends without returning it says that $x$ does not occur at all. The variant is $n - i$ .

Proposition 5.14 (Cost of linear search).

Linear search on an array of $n$ entries makes at most $n$ comparisons with $x$ , and exactly $n$ when $x$ does not occur. If $x$ occurs exactly once, at each of the $n$ positions with equal likelihood, the mean number of comparisons is $(n+1)/2$ . So linear search takes $\Theta(n)$ time in the worst case and on average.

Discussion.

Each pass makes one comparison, and the pass for $i$ is reached only if $x$ was not among the first $i$ entries, so the count is the position at which the search stops, plus one. The worst case is an absent key, which runs through all $n$ passes. For the mean, a key at position $i$ costs $i + 1$ comparisons, and averaging $1, 2, \ldots, n$ is the sum of an arithmetic progression divided by $n$ .

Proof.

The loop makes one comparison per pass and at most $n$ passes, and it makes all $n$ when no entry has key $x$ . If $x$ occurs exactly once, at position $i$ , the search stops after the $(i+1)$ st comparison. Averaging over the $n$ equally likely positions and using the sum of an arithmetic progression,

\frac{1}{n}\sum_{i=0}^{n-1} (i + 1) = \frac{1}{n} \cdot \frac{n(n+1)}{2} = \frac{n+1}{2} .

Each comparison and each pass cost a bounded number of elementary operations, so the running time is $\Theta(n)$ in both the worst case and the mean.

On an unsorted array no comparison algorithm does better. We prove this with an adversary, as in the second proof of the proposition on finding a maximum.

Proposition 5.15 (Searching an unsorted array).

Every deterministic algorithm that decides whether $x$ occurs in an array of $n$ entries, and learns about the entries only by comparing them with $x$ , compares $x$ with all $n$ entries on some input.

Discussion.

An adversary answers every comparison as though the entry compared were larger than $x$ , and fixes the entries only as far as those answers require. If the algorithm stops before comparing $x$ with some entry, that entry is still free. The adversary then sets it equal to $x$ if the algorithm answered “absent”, and to anything else if it answered “present at that entry”, and in either case the answers given stay true while the output becomes wrong.

Proof.

Answer every comparison of $x$ with an entry $T[j]$ as $x < \operatorname{key}(T[j])$ . Suppose that on these answers the algorithm stops having compared $x$ with only some of the entries, and let $T[k]$ be one it never compared. Every compared entry can be given a key larger than $x$ , consistently with all the answers. If the algorithm reports that $x$ does not occur, give $T[k]$ the key $x$ : the answers are unchanged, so a deterministic algorithm gives the same wrong report. If it reports an index $i$ , then either $T[i]$ was compared and has key larger than $x$ , or $i = k$ and we give $T[k]$ a key different from $x$ ; in both cases the report is wrong. So on some input every entry is compared with $x$ .

Problem 5.5.

Suppose that $x$ is absent with probability $\tfrac12$ , and otherwise lies at each of the $n$ positions with probability $\tfrac{1}{2n}$ . Find the mean number of comparisons made by linear search.

Problem 5.6.

A sentinel search appends $x$ at the end of the array before searching, so that the loop needs no test of the index against $n$ . Write it in Python using append and pop, show that it is correct, and count its comparisons of keys and of indices, compared with the linear search above.

Binary Search

When the array is sorted we can search it by bisection, as in Lesson 3, halving a range of positions instead of an interval of reals.

Let $T[0], \ldots, T[n-1]$ be sorted in nondecreasing key order, meaning $\operatorname{key}(T[0]) \leqslant \operatorname{key}(T[1]) \leqslant \cdots \leqslant \operatorname{key}(T[n-1])$ . Binary search for a target key $x$ keeps a candidate interval of positions $[L, R)$ , that is $L \leqslant i < R$ . It compares $x$ with the key at the middle position $m = L + \lfloor (R - L)/2 \rfloor$ . If they are equal it returns $m$ ; if $x$ is smaller it sets $R = m$ ; otherwise it sets $L = m + 1$ . It returns $-1$ when the interval is empty, $L = R$ .

Binary Search
Input:  an array T[0], …, T[n − 1] sorted by key, and a key x.
Output: an index m with key(T[m]) = x, or −1 if there is none.

    L ≝ 0;  R ≝ n
    while L < R do
        m ≝ L + ⌊(R − L) / 2⌋
        if x = key(T[m]) then return m
        if x < key(T[m]) then R ≝ m
        else L ≝ m + 1
    return −1

def binary_search(T, x):
    L, R = 0, len(T)
    while L < R:
        m = L + (R - L) // 2
        if x == T[m]:
            return m
        if x < T[m]:
            R = m
        else:
            L = m + 1
    return -1

T = [2, 3, 5, 7, 11, 13, 17]
print(binary_search(T, 11), binary_search(T, 4))   # 4 -1

The invariant is: if $x$ occurs in $T$ , then at least one matching index lies in $[L, R)$ . It holds initially, when the interval is the whole array. Sortedness maintains it: if $x < \operatorname{key}(T[m])$ then every position from $m$ on has key at least $\operatorname{key}(T[m]) > x$ and can be discarded, and symmetrically when $x > \operatorname{key}(T[m])$ . At termination either a match has been returned or $[L, R)$ is empty, and then by the invariant $x$ does not occur. The length $R - L$ is a variant: it strictly decreases at every pass. We count one comparison per pass, a three-way comparison of $x$ with $\operatorname{key}(T[m])$ whose outcomes are smaller, equal and larger.

Theorem 5.16 (Binary search takes $O(\log n)$ comparisons).

For $n \geqslant 1$ , binary search on a sorted array of length $n$ makes at most $\lfloor \log_2 n \rfloor + 1$ passes of its loop.

Discussion.

The proof is the one for the convergence of bisection, with the length of the interval in place of its width. Because the middle position is removed from the interval, a pass leaves at most $\lfloor \ell/2 \rfloor$ of the $\ell$ positions rather than exactly half. After $t$ passes the length is therefore at most $\lfloor n/2^t \rfloor$ , which is zero once $2^t > n$ , and the least such $t$ is $\lfloor \log_2 n \rfloor + 1$ .

Proof.

Let $\ell = R - L \geqslant 1$ at the start of a pass, so that $m - L = \lfloor \ell/2 \rfloor$ . If the pass does not return, the new interval is $[L, m)$ , of length $\lfloor \ell/2 \rfloor$ , or $[m+1, R)$ , of length $\ell - \lfloor \ell/2 \rfloor - 1 = \lceil \ell/2 \rceil - 1 \leqslant \lfloor \ell/2 \rfloor$ . So after each pass the length is at most $\lfloor \ell / 2 \rfloor$ , and since $\bigl\lfloor \lfloor a \rfloor / 2 \bigr\rfloor = \lfloor a/2 \rfloor$ for $a \geqslant 0$ , after $t$ passes it is at most $\lfloor n / 2^t \rfloor$ . For $t = \lfloor \log_2 n \rfloor + 1$ we have $2^t > n$ , so the length is $0$ and the loop has stopped.

The bound is attained, for example by an unsuccessful search for a key smaller than every key in the array: it moves left at every pass, and the length goes $n, \lfloor n/2 \rfloor, \lfloor n/4 \rfloor, \ldots$ down to $0$ .

Figure 5.5. The indices binary search tests on an array of length

7

. A search starts at the root and moves left when the target is smaller than the tested key and right when it is larger; it may stop at any vertex on finding the target.

For $n = 7 = 2^3 - 1$ the positions tested form the binary tree of Figure 5.5: the root is the first position tested, and the left and right children of a position are the ones tested next when the target is smaller or larger. A search that stops at depth $t$ has made $t + 1$ comparisons.

Proposition 5.17 (Mean cost of a successful search).

Let $n = 2^k - 1$ and suppose the target is one of the $n$ keys, each equally likely, with all keys distinct. The mean number of comparisons made by binary search is

\frac{1}{2^k - 1} \sum_{i=1}^{k} i\, 2^{i-1} = k - 1 + \frac{k}{2^k - 1} .

Discussion.

For $n = 2^k - 1$ every interval that arises has odd length and splits into two equal halves, so the tree of tested positions is full, with $2^{i-1}$ positions at depth $i - 1$ for $i = 1, \ldots, k$ , and a target at depth $i - 1$ is found after $i$ comparisons. That gives the sum. To evaluate $S_k = \sum_{i=1}^{k} i\,2^{i-1}$ we proceed as for the geometric sum and compare $S_k$ with $2S_{k-1}$ , whose terms are those of $S_k$ shifted by one place with the multiplier lowered by one, so that the difference is a geometric sum.

Proof.

An interval of length $2^j - 1$ with $j \geqslant 2$ has middle position with $2^{j-1} - 1$ positions on each side, so by induction on $j$ the positions tested form a full binary tree with $2^{i-1}$ positions at depth $i - 1$ , for $1 \leqslant i \leqslant k$ . The target at a position of depth $i - 1$ is found at the $i$ th comparison, so the total over the $n$ equally likely targets is $S_k = \sum_{i=1}^{k} i\,2^{i-1}$ .

For $k \geqslant 2$ ,

S_k - 2S_{k-1} = \sum_{i=1}^{k} i\,2^{i-1} - \sum_{i=2}^{k} (i-1)\,2^{i-1} = 1 + \sum_{i=2}^{k} 2^{i-1} = 2^k - 1

by the geometric sum. So $S_k = 2S_{k-1} + 2^k - 1$ with $S_1 = 1$ , and induction gives $S_k = (k-1)2^k + 1$ : at $k = 1$ both sides are $1$ , and $2\bigl((k-2)2^{k-1} + 1\bigr) + 2^k - 1 = (k-1)2^k + 1$ . Finally $(k-1)2^k + 1 = (k-1)(2^k - 1) + k$ , and dividing by $2^k - 1$ gives the stated mean.

The mean is $\Theta(\log n)$ . For arbitrary $n$ interval halving gives an $O(\log n)$ worst case, by the theorem. For a lower bound on the mean, the positions found within $t$ comparisons are those of depth less than $t$ in the tree of tested positions, and by the proposition on binary trees there are at most $2^t - 1$ of them. Take $t = \lfloor \log_2 n \rfloor - 1$ for $n \geqslant 4$ ; then $2^t - 1 < n/2$ , so fewer than half the $n$ positions are found within $t$ comparisons. At least half need more than $t$ , and the mean over equally likely targets is $\Omega(\log n)$ .

A Lower Bound for Searching

A deterministic comparison search algorithm can be pictured as a fixed binary decision tree of all its possible executions, in which each internal vertex is a comparison the algorithm makes. The algorithm walks down the tree from the root: the first comparison it makes is at the root, and according to the outcome it continues at one of the two children. It stops on reaching a leaf, which records its output, so there must be a leaf for every possible output. The number of comparisons on a given input is the depth of the leaf reached, and the worst-case number is the height of the tree.

Theorem 5.18 (Searching needs $\Omega(\log n)$ comparisons).

Every deterministic algorithm that searches a set of $n$ items with distinct keys for a given key, using only comparisons of keys, makes at least $\lceil \log_2(n+1) \rceil$ comparisons on some input.

Discussion.

The proof counts outputs. A search can end in $n + 1$ different ways, one for each stored item and one for “not present”, and each must appear at some leaf of the decision tree. A binary tree with that many leaves has height at least $\log_2(n+1)$ by the corollary on heights, and height is the worst-case number of comparisons.

Proof.

The algorithm has $n + 1$ possible outputs, the $n$ stored items and the report that no item has the key, and each occurs for some input, so its decision tree has at least $n + 1$ leaves. By the corollary on heights of binary trees its height is at least $\lceil \log_2(n+1) \rceil$ , and some input follows a path of that length.

So binary search makes the least possible number of comparisons, up to a constant factor. The same argument with any fixed number of outcomes per comparison in place of two still gives $\Omega(\log n)$ . Hashing does better because it is not a comparison algorithm: reading a direct access array at an index computed from the key can go to any one of its slots in a single step.

Problem 5.7.

Modify binary_search so that it returns the least index $i$ with $\operatorname{key}(T[i]) \geqslant x$ , or $n$ if there is none, still in $O(\log n)$ time. State the invariant, and use your function to count the entries of a sorted array lying in an interval $[a, b)$ .

Problem 5.8.

A programmer writes L = m in place of L = m + 1. Give an array and a key for which the modified loop never terminates, and say which part of the termination argument fails.

Sorting

The Sorting Problem

We sort records, each carrying a key that can be compared with other keys. A comparison sort learns about the keys only by comparing them, as in the comparison model.

Definition 5.19 (Sorting, in place and stable).

A sort returns the same records as its input, rearranged in nondecreasing key order. A sort is in place if it uses $O(1)$ auxiliary cells besides the input array, apart from stack space for recursion if that is being counted separately. A sort is stable if records with equal keys keep their input order.

Checking only that the output keys are in order is not enough to certify a sort: the output must also be a rearrangement of the input records, with none lost or duplicated. Stability can be forced in any comparison sort by comparing the pairs $(\text{key}, \text{original index})$ lexicographically, first by key and then by index, though storing the original indices may change the space requirements.

Example 5.20 (Stable and unstable).

Sorting $(2, a), (1, b), (2, c)$ stably by the numeric key gives $(1, b), (2, a), (2, c)$ : the two records with key $2$ remain in their original relative order. A routine that returns $(1, b), (2, c), (2, a)$ has sorted the records, but not stably.

A rearrangement of $n$ records is a permutation, written as the list $\pi_1, \ldots, \pi_n$ of the input positions in output order, and there are $n!$ of them. A brute-force method tests permutations one by one until it finds an arrangement in increasing order of pairwise distinct keys. A candidate may need $n - 1$ comparisons of adjacent keys to certify that it is sorted, and there are $n!$ candidates.

Definition 5.21 (Inversion).

An inversion of an array $T[0], \ldots, T[n-1]$ is a pair of positions $i < j$ with $\operatorname{key}(T[i]) > \operatorname{key}(T[j])$ .

A sorted array has no inversions, and an array of distinct keys in decreasing order has all $\binom{n}{2}$ possible ones, one for each unordered pair of positions. An exchange of two adjacent records $T[j], T[j+1]$ with $\operatorname{key}(T[j]) > \operatorname{key}(T[j+1])$ removes exactly one inversion, that pair itself, since the relative order of every other pair is unchanged.

Selection Sort

Selection sort repeatedly removes the largest remaining key and puts it at the next final position from right to left. Having already sorted the largest items into the subarray A[i+1:], it scans A[:i+1] for the largest item not yet placed and swaps it with A[i].

Selection Sort
Input:  an array A[0], …, A[n − 1].
Output: the same array, sorted.

    for i ≝ n − 1 down to 1 do
        m ≝ i
        for j ≝ 0 to i − 1 do
            if key(A[m]) < key(A[j]) then m ≝ j
        swap A[m] and A[i]

def selection_sort(A):
    for i in range(len(A) - 1, 0, -1):   # O(n) passes
        m = i                            # O(1) index of the largest so far
        for j in range(i):               # O(i) search A[:i] for a larger item
            if A[m] < A[j]:              # O(1)
                m = j                    # O(1) new largest found
        A[m], A[i] = A[i], A[m]          # O(1) swap

A = [5, 2, 9, 1, 5, 6]
selection_sort(A)
print(A)   # [1, 2, 5, 5, 6, 9]

The invariant before the pass for $i$ is that A[i+1:] holds the $n - 1 - i$ largest records in sorted order, and that every key in A[:i+1] is at most every key in A[i+1:]. The pass moves the largest key of A[:i+1] to position $i$ , which extends the sorted suffix by one. When the loop ends, at $i = 0$ , the suffix A[1:] is sorted and A[0] holds the smallest key.

Finding the maximum among $k$ remaining keys takes $k - 1$ comparisons, which is the least possible by the proposition on finding a maximum, so the method uses

\sum_{k=1}^{n} (k - 1) = \frac{n(n-1)}{2} = \Theta(n^2)

comparisons, even on an input that is already sorted. It performs at most $n - 1$ swaps. It is in place: apart from the array it uses the names i, j and m.

Example 5.22 (Selection on $(1, 2, 4)$ ).

On $(1, 2, 4)$ , selection chooses $4$ , then $2$ , then $1$ . Each chosen maximum occupies its final, rightmost open position, and the comparison counts are $2 + 1 + 0 = 3$ .

Selection sort, swapping as above, is not stable. On the records $(2, a), (1, b), (1, c)$ , compared by key alone, the first pass finds $(2, a)$ at position $0$ as the maximum and swaps it with $(1, c)$ at position $2$ , giving $(1, c), (1, b), (2, a)$ ; the second pass makes no change, and $(1, c)$ ends before $(1, b)$ .

Bubble Sort

A left-to-right pass of bubble sort compares $T[j]$ with $T[j+1]$ and exchanges them if they are out of order. The largest key in the scanned part moves to its right end, so a full pass places the maximum of the active prefix at its final position. Repeating on successively shorter prefixes sorts the array. If a pass makes no exchange, the array is already sorted and the algorithm can stop early.

Bubble Sort
Input:  an array T[0], …, T[n − 1].
Output: the same array, sorted.

    for last ≝ n − 1 down to 1 do
        changed ≝ false
        for j ≝ 0 to last − 1 do
            if key(T[j]) > key(T[j + 1]) then
                swap T[j] and T[j + 1];  changed ≝ true
        if not changed then stop

def bubble_sort(T):
    for last in range(len(T) - 1, 0, -1):
        changed = False
        for j in range(last):
            if T[j] > T[j + 1]:
                T[j], T[j + 1] = T[j + 1], T[j]
                changed = True
        if not changed:
            return

The invariant before the pass with a given last is that T[last+1:] holds the largest records in sorted order, each at least every key in T[:last+1].

For $n \geqslant 1$ , the worst-case number of comparisons is $n(n-1)/2$ , and the best case, on a sorted input, is $n - 1$ with the early stop. Over the $n!$ orders of $n$ distinct keys, counted equally, the mean number of comparisons is still $\Theta(n^2)$ . For the lower bound, the smallest key begins in the last half of the array, at one of the $\lceil n/2 \rceil$ positions from $\lfloor n/2 \rfloor$ on, in at least half of the $n!$ orders. A left-to-right pass moves the smallest key left by at most one position, so on those orders at least $\lfloor n/2 \rfloor$ passes are needed, and each of those passes makes at least $n/2$ comparisons. Thus at least half the orders cost at least $\lfloor n/2 \rfloor \cdot n/2$ comparisons, and the mean is $\Omega(n^2)$ . The upper bound $O(n^2)$ holds on every input.

Proposition 5.23 (Exchanges in bubble sort).

The number of exchanges bubble sort makes on an array equals its number of inversions. Over the $n!$ orders of $n$ distinct keys, counted equally, the mean number of inversions is $n(n-1)/4$ .

Discussion.

For the first statement, every exchange removes exactly one inversion, and the algorithm stops with a sorted array, which has none; so the number of exchanges is the number of inversions at the start. For the mean, pair each order with its reverse. A pair of positions is inverted in exactly one of the two, so the inversion counts of an order and of its reverse add up to $\binom{n}{2}$ . The reversal pairs the $n!$ orders off, so the average over all of them is half of $\binom{n}{2}$ .

Proof.

Bubble sort exchanges $T[j]$ and $T[j+1]$ only when $\operatorname{key}(T[j]) > \operatorname{key}(T[j+1])$ , and such an exchange of adjacent records removes exactly one inversion. It stops with a sorted array, which has no inversions. So if the input has $I$ inversions, it makes exactly $I$ exchanges.

For an order $\pi$ of distinct keys let $\operatorname{inv}(\pi)$ be its number of inversions, and let $\bar\pi$ be the reverse order. For each of the $\binom{n}{2}$ pairs of keys, exactly one of $\pi$ and $\bar\pi$ lists the larger key first, so $\operatorname{inv}(\pi) + \operatorname{inv}(\bar\pi) = \binom{n}{2}$ . Reversal is a bijection from the set of orders to itself, so summing over all orders,

2\sum_{\pi} \operatorname{inv}(\pi) = \sum_{\pi} \bigl(\operatorname{inv}(\pi) + \operatorname{inv}(\bar\pi)\bigr) = n!\binom{n}{2},

and the mean is $\tfrac12\binom{n}{2} = n(n-1)/4$ .

Exchanges happen only on strict inversions, so records with equal keys are never exchanged with each other and keep their original order: bubble sort is stable. Small keys near the right end move slowly, one position per pass, and are sometimes called turtles; large keys near the left move quickly to the right and are called hares. Bidirectional bubble sort alternates the direction of its passes to move turtles faster, and gnome sort steps back to recheck the previous adjacent pair after each exchange.

Insertion Sort

Insertion sort treats T[0..i-1] as sorted and inserts T[i] into that prefix by shifting the larger records one position right.

Insertion Sort
Input:  an array T[0], …, T[n − 1].
Output: the same array, sorted.

    for i ≝ 1 to n − 1 do
        x ≝ T[i];  j ≝ i − 1
        while j ⩾ 0 and key(x) < key(T[j]) do
            T[j + 1] ≝ T[j];  j ≝ j − 1
        T[j + 1] ≝ x

def insertion_sort(T):
    for i in range(1, len(T)):           # O(n) passes
        x = T[i]                         # the record to insert
        j = i - 1
        while j >= 0 and x < T[j]:       # O(i) shift larger records right
            T[j + 1] = T[j]
            j = j - 1
        T[j + 1] = x                     # fill the gap

The invariant before the pass for $i$ is that T[0..i-1] holds the first $i$ input records in sorted order. The final assignment T[j+1] = x places the saved record in the gap left by the shifts, and it is essential: writing $x$ anywhere else would duplicate one record and lose another. The while test relies on and stopping as soon as j >= 0 is False, so that T[-1] is never read.

Example 5.24 (Insertion on $(4, 2, 3)$ ).

On $(4, 2, 3)$ , save $2$ , shift $4$ right and write $2$ at index $0$ , giving $(2, 4, 3)$ . Next save $3$ , shift $4$ right and write $3$ at index $1$ , giving $(2, 3, 4)$ .

Insertion sort is $\Theta(n^2)$ in the worst case, on an input in decreasing order, where the pass for $i$ shifts all $i$ records of the prefix, and $\Theta(n)$ on an already sorted input, where every pass makes one comparison and no shift.

In Place and Stable

Selection sort, bubble sort and insertion sort are all in place: each uses a constant amount of space besides the array, and acts on the array only by comparisons and by exchanging or moving records. Bubble sort and insertion sort are stable, insertion sort because a record is never shifted past one with an equal key. Selection sort, as implemented above, is not.

Problem 5.9.

Show that insertion sort performs exactly as many shifts T[j + 1] = T[j] as the input has inversions, and deduce the mean number of shifts over the $n!$ orders of $n$ distinct keys. Give an input of length $n$ on which selection sort makes $n - 1$ swaps and insertion sort makes no shift.

Problem 5.10.

Run bubble sort and insertion sort on $(3, 1, 4, 1, 5, 9, 2, 6)$ , keeping the two $1$ s apart as $1_a$ and $1_b$ . Record the array after each pass of each algorithm, count the comparisons and exchanges or shifts, and confirm that both outputs keep $1_a$ before $1_b$ .

Merge Sort

Merge sort splits the array in half, sorts each half recursively, and merges the two sorted halves into one.

Proposition 5.25 (Merging two sorted arrays).

Two sorted arrays of lengths $a, b > 0$ can be merged into one sorted array with at most $a + b - 1$ key comparisons. If ties take the record from the left array first, the merge is stable.

Discussion.

The smallest remaining record of the whole is always at the front of one of the two arrays, because each array is sorted, so one comparison of the two front records decides which comes next. Each comparison outputs one record, and once one array is exhausted the rest of the other is copied without comparing. At least one record, the last, is output without a comparison, which gives $a + b - 1$ . For stability, when the two front keys are equal, taking the left one keeps records from the left array ahead of equal records from the right.

Proof.

Keep a cursor at the first unmerged element of each array. While both arrays have elements left, compare their current heads and copy the smaller one to the output. Its key is no larger than any remaining key, because each input array is already sorted. So the output stays sorted, and no record is lost or copied twice. Each comparison advances one cursor, so after at most $a + b - 1$ comparisons one array must be empty; the other array’s sorted tail is then appended without further comparisons. On equal keys, choosing the left head first preserves the original order between the two arrays, while the order within each array is unchanged.

Merge
Input:  sorted arrays X and Y.
Output: a sorted array Z holding the records of X and Y.

    i ≝ 0;  j ≝ 0;  Z ≝ empty
    while i < length(X) and j < length(Y) do
        if key(X[i]) ⩽ key(Y[j]) then append X[i] to Z;  i ≝ i + 1
        else append Y[j] to Z;  j ≝ j + 1
    append the remaining part of X, then of Y, to Z
    return Z

Merge Sort
Input:  an array A.
Output: a sorted array holding the records of A.

    if length(A) ⩽ 1 then return A
    h ≝ ⌊length(A) / 2⌋
    return Merge(Merge Sort(A[0..h − 1]), Merge Sort(A[h..length(A) − 1]))

def merge(X, Y):
    i, j, Z = 0, 0, []
    while i < len(X) and j < len(Y):
        if X[i] <= Y[j]:
            Z.append(X[i])
            i = i + 1
        else:
            Z.append(Y[j])
            j = j + 1
    return Z + X[i:] + Y[j:]

def merge_sort(A):
    if len(A) <= 1:
        return A
    h = len(A) // 2
    return merge(merge_sort(A[:h]), merge_sort(A[h:]))

print(merge_sort([15, 5, 64, 8, 12, 6, 4, 35]))   # [4, 5, 6, 8, 12, 15, 35, 64]

Theorem 5.26 (Merge sort).

On an array of $n$ records with comparable keys, merge sort returns a sorted rearrangement of the input, and choosing the left head on equal keys makes it stable. It uses $O(n \log n)$ time and $O(n)$ auxiliary storage. For $n = 2^k$ , its worst-case number of key comparisons is exactly $n \log_2 n - n + 1$ .

Discussion.

Correctness is an induction on $n$ whose step is the merge proposition: the recursive calls are on shorter arrays, so by the hypothesis they return sorted rearrangements of the halves, and merging those gives a sorted rearrangement of the whole. For the time, we count level by level: the arrays at one level are disjoint pieces of the input, so merging all of them costs $O(n)$ , and halving gives about $\log_2 n$ levels. For the exact count, the merge proposition allows a merge of two halves of size $2^{k-1}$ up to $2^k - 1$ comparisons, which gives the recurrence $C_k = 2C_{k-1} + 2^k - 1$ . It remains to find an input that attains the bound at every merge, and to solve the recurrence.

Proof.

We prove correctness by induction on $n$ . For $n \leqslant 1$ the array is already sorted. If $n > 1$ , both halves have fewer than $n$ elements, so the recursive calls terminate and, by induction, return sorted rearrangements of their halves. The merge proposition combines those into a sorted rearrangement of the whole input. Its tie rule preserves the order of equal-key records across the halves, so induction also proves stability. The recursion terminates because every call on more than one record is made on strictly shorter arrays.

At any fixed level of the recursion the subarrays are disjoint parts of the original array, so their lengths add up to at most $n$ . Merging each costs time proportional to its length, so the total work per level is $O(n)$ . Halving gives at most $\lceil \log_2 n \rceil$ levels of merging, and therefore $O(n \log n)$ time. At any instant the arrays alive along the current chain of calls have lengths at most $n, n/2, n/4, \ldots$ together with their merge outputs, so at most $O(n)$ auxiliary storage is present at once; the recursion stack has $O(\log n)$ frames.

When $n = 2^k$ , a merge of two sorted halves of equal size can need all $2^k - 1$ comparisons the merge proposition allows: give the left half the records of odd rank and the right half those of even rank, so that their sorted values alternate until only one remains. Apply the same odd–even assignment recursively within each half. Arranging the input by these assignments makes every merge attain its worst case. Writing $C_k$ for the worst case at size $2^k$ , this gives $C_0 = 0$ and

C_k = 2C_{k-1} + 2^k - 1 .

We claim $C_k = k2^k - 2^k + 1$ . At $k = 0$ both sides are $0$ . Assuming the formula at $k - 1$ ,

C_k = 2\bigl((k-1)2^{k-1} - 2^{k-1} + 1\bigr) + 2^k - 1 = k2^k - 2^k + 1 .

With $n = 2^k$ this is $n \log_2 n - n + 1$ . It is a count of key comparisons, and an array of one record makes none.

Problem 5.11.

Write an iterative merge sort that merges adjacent runs of length $1$ , then $2$ , then $4$ , and so on, with no recursion. Prove it correct with a loop invariant on the run length, and show that it makes at most $n \lceil \log_2 n \rceil$ comparisons.

Quicksort

Quicksort chooses a pivot, partitions the array so that smaller keys precede the pivot and larger or equal keys follow it, and then recursively sorts the two sides. For the partition in place, with the pivot initially at position $L$ , the invariant before inspecting position $k$ is: positions $L+1, \ldots, p$ hold keys smaller than the pivot, positions $p+1, \ldots, k-1$ hold keys larger than or equal to it, and positions $k, \ldots, R-1$ are unexamined. A newly found smaller record is swapped into position $p + 1$ and $p$ is increased. At the end the pivot is swapped with the record at position $p$ . Partitioning $s$ records compares each of the other $s - 1$ records with the pivot once.

The pseudocode below sorts the half-open slice $[L, R)$ of the original array in place; no slice is copied. The partition moves only records strictly smaller than the pivot to its left.

Quicksort
Input:  an array A and positions L ⩽ R.
Output: A with A[L..R − 1] sorted.

    Sort(A, L, R):
        if R − L ⩽ 1 then return
        choose q uniformly from L, …, R − 1;  swap A[L] and A[q]
        pivot ≝ A[L];  p ≝ L
        for k ≝ L + 1 to R − 1 do
            if key(A[k]) < key(pivot) then
                p ≝ p + 1;  swap A[p] and A[k]
        swap A[L] and A[p]
        Sort(A, L, p);  Sort(A, p + 1, R)

The statement from random import randrange makes randrange available: randrange(L, R) returns an integer chosen uniformly from $L, \ldots, R - 1$ , the same range as range(L, R).

from random import randrange

def sort_slice(A, L, R):
    if R - L <= 1:
        return
    q = randrange(L, R)
    A[L], A[q] = A[q], A[L]
    pivot = A[L]
    p = L
    for k in range(L + 1, R):
        if A[k] < pivot:
            p = p + 1
            A[p], A[k] = A[k], A[p]
    A[L], A[p] = A[p], A[L]
    sort_slice(A, L, p)
    sort_slice(A, p + 1, R)

def quicksort(A):
    sort_slice(A, 0, len(A))

If the pivot has rank $r$ among $n$ distinct keys, meaning $r - 1$ keys are smaller, the number of comparisons satisfies

C(n) = n - 1 + C(r - 1) + C(n - r), \qquad C(0) = C(1) = 0 .

Example 5.27 (One partition).

For the input $(15, 5, 64, 8, 12, 6, 4, 35)$ , take the first value $15$ as pivot, with no random swap. The partition puts the five smaller values $5, 8, 12, 6, 4$ before it and $64, 35$ after it, and the in-place result is $(4, 5, 8, 12, 6, 15, 64, 35)$ . Recursively sorting the two sides gives $(4, 5, 6, 8, 12, 15, 35, 64)$ . The order within each side before the recursion depends on the partition routine.

Proposition 5.28 (Worst and best case of quicksort).

For $n$ distinct keys, any run of quicksort makes at most $\binom{n}{2} = n(n-1)/2$ key comparisons. This bound is attained when every pivot is the smallest or largest key in its current subarray, so the worst-case number of comparisons is $\Theta(n^2)$ . If every pivot splits its subarray as evenly as possible, the number of comparisons is $\Theta(n \log n)$ .

Discussion.

For the upper bound we count pairs of keys. Two keys are compared only when one of them is the pivot, and a pivot is left out of all later calls, so no pair is compared twice; there are $\binom{n}{2}$ pairs. When every pivot is extreme, one side of each partition is empty, and the recurrence becomes $W_n = (n-1) + W_{n-1}$ , which sums to the same number. For even splits, the depth of the recursion is logarithmic and each level costs at most $n$ comparisons, which gives $O(n \log n)$ ; the matching lower bound needs a count of how many levels still have large subarrays, and how many comparisons each such level makes.

Proof.

Partitioning a subarray of size $s$ compares its pivot with each of the other $s - 1$ keys exactly once. A given pair of keys can be compared only when one of them is the pivot, and that pivot is then excluded from all recursive subarrays. Thus no pair is compared twice, and there are at most $\binom{n}{2}$ comparisons. If every pivot is extreme, one recursive side is empty and the other has size $n - 1$ . The count obeys $W_n = (n-1) + W_{n-1}$ with $W_0 = W_1 = 0$ , and hence

W_n = (n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2} .

For balanced splits, the recursion has $O(\log n)$ levels. At any level the active subarrays are disjoint, so their sizes add up to at most $n$ and their partitions make at most $n$ comparisons in total. This proves $O(n \log n)$ .

For the reverse bound, number the levels from $\ell = 0$ . A balanced split of $s$ records leaves at least $\lfloor (s-1)/2 \rfloor$ records on either side. Applying this at each level shows that every subarray at level $\ell$ has at least $\lfloor (n+1)/2^\ell \rfloor - 1$ records. For $0 \leqslant \ell \leqslant \lfloor \log_2 n \rfloor - 2$ this is at least $3$ , so no branch has yet ended at a call on one record. Before such a level at most $2^\ell - 1$ pivots have been removed, and the remaining records all belong to at most $2^\ell$ active subarrays. A subarray of size $s$ uses $s - 1$ comparisons, so level $\ell$ uses at least $n - (2^\ell - 1) - 2^\ell = n - 2^{\ell+1} + 1 \geqslant n/2$ comparisons. There are $\Theta(\log n)$ such levels for large $n$ , which proves $\Omega(n \log n)$ .

The in-place partition is not stable in general. The recursive calls use $O(\log n)$ stack space for balanced splits and $O(n)$ when the splits are as uneven as possible.

With a random pivot the cost is an average over the random choices, in the sense of the expectation defined for hashing in the last lesson.

Remark (Expected cost of a randomized algorithm).

The expectation used for hashing is an average over one uniform choice. Randomized quicksort makes a uniform choice at every call, and its expected cost is defined in the same way one call at a time: if a call on $s$ keys chooses the pivot rank $r$ with probability $1/s$ , and the rest of the run then has expected cost $c_r$ , the expected cost of the call is its own comparisons plus $\tfrac{1}{s}\sum_{r} c_r$ . Equivalently, it is the average over all complete runs, each run weighted by the product of the probabilities $1/s$ of the choices it makes.

Theorem 5.29 (Expected cost of randomized quicksort).

Fix any input order of $n$ distinct keys. At every recursive call choose the pivot uniformly from the current subarray, and compare it once with each other key there. Let $E_n$ be the expected total number of key comparisons. Then

E_0 = 0, \qquad E_n = 2(n+1)H_n - 4n \quad (n \geqslant 1) .

In particular $E_n = \Theta(n \log n)$ . The expectation is over the pivot choices; the input order is fixed and need not be random.

Discussion.

The proof has four steps. Conditioning on the rank of the first pivot turns the expectation into a recurrence in which $E_n$ depends on all of $E_0, \ldots, E_{n-1}$ through their sum. Writing the recurrence at $n$ and at $n - 1$ and subtracting removes the sum, leaving a first-order recurrence with variable coefficients, of the kind the summation factor of the last lesson solves; the example there is the same recurrence with $2n$ in place of $2(n-1)$ . Here the answer is checked by induction instead. Finally the bounds on $H_n$ give the growth rate.

Proof.

Step 1: condition on the first pivot. A subarray of size at most $1$ needs no comparisons, so $E_0 = E_1 = 0$ . For $n \geqslant 2$ the first partition costs exactly $n - 1$ comparisons. The pivot is equally likely to have any rank $r \in \{1, \ldots, n\}$ among the keys. Rank $r$ leaves $r - 1$ smaller keys on the left and $n - r$ larger keys on the right. Because every later pivot is chosen uniformly within its own subarray, the expected costs of those two calls are $E_{r-1}$ and $E_{n-r}$ , whatever their internal order. Averaging over the $n$ possible ranks gives

E_n = \frac{1}{n}\sum_{r=1}^{n} \bigl((n-1) + E_{r-1} + E_{n-r}\bigr) = n - 1 + \frac{2}{n}\sum_{j=0}^{n-1} E_j ,

since both $r - 1$ and $n - r$ run once through $0, \ldots, n-1$ as $r$ runs through $1, \ldots, n$ .

Step 2: remove the sum. Multiply this equation by $n$ , and write the same equation for $n - 1$ multiplied by $n - 1$ :

\begin{aligned} nE_n &= n(n-1) + 2\sum_{j=0}^{n-1} E_j, \\ (n-1)E_{n-1} &= (n-1)(n-2) + 2\sum_{j=0}^{n-2} E_j . \end{aligned}

Subtract the second from the first. The two sums differ only by $E_{n-1}$ , while $n(n-1) - (n-1)(n-2) = 2(n-1)$ . Therefore $nE_n - (n-1)E_{n-1} = 2(n-1) + 2E_{n-1}$ , that is,

nE_n = (n+1)E_{n-1} + 2(n-1) .

Step 3: solve by induction. At $n = 1$ the claimed expression is $2 \cdot 2 \cdot H_1 - 4 = 0 = E_1$ . Assume $E_{n-1} = 2nH_{n-1} - 4(n-1)$ for some $n \geqslant 2$ . Substituting into the last recurrence and using $H_{n-1} = H_n - 1/n$ ,

\begin{aligned} nE_n &= (n+1)\bigl(2nH_{n-1} - 4(n-1)\bigr) + 2(n-1) \\ &= 2n(n+1)H_{n-1} - 4n^2 + 2n + 2 \\ &= 2n(n+1)\left(H_n - \frac{1}{n}\right) - 4n^2 + 2n + 2 \\ &= 2n(n+1)H_n - 4n^2 . \end{aligned}

Dividing by $n$ gives $E_n = 2(n+1)H_n - 4n$ .

Step 4: the growth rate. By the bounds on the harmonic numbers, $\tfrac12\lfloor \log_2 n \rfloor \leqslant H_n \leqslant 1 + \log_2 n$ . The upper bound gives $E_n \leqslant 2(n+1)(1 + \log_2 n) = O(n \log n)$ . The lower bound gives $E_n \geqslant (n+1)(\log_2 n - 1) - 4n$ , and for all sufficiently large $n$ the term $(n+1)\log_2 n$ exceeds twice the rest, so $E_n = \Omega(n \log n)$ . Thus $E_n = \Theta(n \log n)$ .

Example 5.30 (Three keys).

For three distinct keys, a smallest or largest first pivot costs two comparisons and leaves a call on two keys costing one more, for a total of $3$ . A middle first pivot costs two comparisons and leaves only calls on one key, for a total of $2$ . The three ranks are equally likely, so $E_3 = (3 + 2 + 3)/3 = 8/3$ . The formula agrees: $2 \cdot 4 \cdot \bigl(1 + \tfrac12 + \tfrac13\bigr) - 12 = 8/3$ .

Problem 5.12.

Show that on the input $(1, 2, \ldots, n)$ quicksort with the first record always taken as pivot makes $n(n-1)/2$ comparisons, and that with a uniformly random pivot the probability of making all $n(n-1)/2$ is $2^{n-1}/n!$ for $n \geqslant 2$ .

Problem 5.13.

Two keys of ranks $i < j$ are compared by randomized quicksort exactly when the first pivot chosen from the keys of ranks $i, \ldots, j$ is one of the two. Deduce that they are compared with probability $2/(j - i + 1)$ , and use linearity of expectation to give a second proof that $E_n = 2(n+1)H_n - 4n$ .

Lower Bounds for Comparison Sorting

A deterministic comparison sort is described, like a comparison search, by a binary decision tree: each internal vertex is a comparison, the two branches below it are its two outcomes, and each leaf records the rearrangement the algorithm outputs. An algorithm may ask a comparison whose result is already forced by earlier answers, and then one branch below it is reached by no input.

Figure 5.6. A comparison tree for three records

a_0, a_1, a_2

. Left branches answer yes and right branches no; a leaf such as

021

means

a_0 \lt a_2 \lt a_1

. The two accented leaves cannot be reached, because the comparison above them was already settled by an earlier answer.

The comparison tree of Figure 5.6 names the compared records $a_0, a_1, a_2$ rather than their changing positions in the array. Its six reachable leaves are the six possible strict orders; the crossed leaves are impossible by transitivity.

Theorem 5.31 (Worst-case lower bound for sorting).

Every deterministic sorting algorithm that learns about $n$ distinct, otherwise arbitrary keys only by comparing pairs makes at least $\lceil \log_2(n!) \rceil$ comparisons on some input. Hence its worst-case number of comparisons is $\Omega(n \log n)$ .

Discussion.

As for searching, the proof counts outputs, and there are now $n!$ of them. Two inputs whose keys are in different relative orders need different rearrangements, so they must reach different leaves, and the decision tree has at least $n!$ reachable leaves. The corollary on heights of binary trees then bounds the height below by $\log_2(n!)$ . For the growth rate, half of the factors of $n!$ are at least $n/2$ , so $\log_2(n!)$ is at least about $\tfrac{n}{2}\log_2 \tfrac{n}{2}$ .

Proof.

There are $n!$ possible relative orders of the distinct input keys: $n$ choices for the rank of the first record, $n - 1$ for the second, and so on. Represent the algorithm by its binary decision tree. Each input follows one path from the root to a leaf, and the length of that path is its number of comparisons. Two different relative orders cannot end at the same leaf: that leaf prescribes one output rearrangement for both, and for at least one of them it is wrong. Therefore the tree has at least $n!$ reachable leaves, and after removing the unreachable branches it is a binary tree with at least $n!$ leaves. By the corollary on heights its height $h$ satisfies $h \geqslant \lceil \log_2(n!) \rceil$ .

The last $\lfloor n/2 \rfloor$ factors of $n! = n(n-1)\cdots 1$ are each at least $n/2$ , so $n! \geqslant (n/2)^{\lfloor n/2 \rfloor}$ and

\log_2(n!) \geqslant \lfloor n/2 \rfloor \log_2(n/2) = \Omega(n \log n) .

Removing the branches that no input can follow, and contracting each vertex left with one child, turns the decision tree into a full binary tree with one leaf per possible outcome.

Figure 5.7. Pruning. Branches that no input can follow are drawn dashed on the left; removing them and contracting each vertex left with a single child gives the full binary tree on the right, with one leaf for each of the four possible outcomes.

Merge sort makes at most $n\lceil \log_2 n\rceil$ comparisons, so it is asymptotically optimal among comparison sorts in the worst case.

The mean number of comparisons over the $n!$ equally weighted orders of distinct keys is the mean depth of the leaves of the decision tree, one leaf per order. A full binary tree with $K$ leaves is balanced if its leaf depths differ by at most one.

Proposition 5.32 (Balanced trees minimise the total depth).

Among full binary trees with $K$ leaves, a balanced one has the least sum of leaf depths, and in a balanced full binary tree with $K$ leaves every leaf has depth at least $\lfloor \log_2 K \rfloor$ .

Discussion.

The first claim is proved by an exchange that lowers the depth sum of an unbalanced tree. If some leaf $c$ is at least two levels above the deepest leaves, move a deepest pair of sibling leaves $a, b$ together with their parent into the place of $c$ , and put $c$ where their parent was. Three depths change, and the sum falls. The depth sum is a nonnegative integer, so the exchange can be repeated only finitely often, and it stops at a balanced tree. For the second claim, look at the shallowest leaf: every level above it is full, and all leaves lie on its level or the next, which bounds $K$ by twice the size of its level.

Proof.

Take a full binary tree that is not balanced. Choose deepest sibling leaves $a, b$ , at depth $p$ , with parent $n$ , and a leaf $c$ at depth $p' \leqslant p - 2$ . Exchange the subtree consisting of $n$ , $a$ and $b$ with the leaf $c$ . The tree remains a full binary tree with the same leaves, $a$ and $b$ move to depth $p' + 1$ , and $c$ moves to depth $p - 1$ . The sum of these three depths changes from $2p + p'$ to $2(p' + 1) + (p - 1)$ , a decrease of $p - p' - 1 > 0$ , and no other depth changes. Repeating the operation reaches a balanced tree, because the nonnegative integer depth sum strictly decreases each time. Every tree with $K$ leaves can be transformed in this way into a balanced one with no larger depth sum, and all balanced full binary trees with $K$ leaves have the same multiset of leaf depths, as the count below shows; so a balanced tree has the least sum.

Let the shallowest leaf of a balanced full binary tree have depth $d$ . There is no leaf above depth $d$ , so every vertex at depth less than $d$ is internal with two children, and depth $d$ holds $2^d$ vertices. The leaves are at depth $d$ or $d + 1$ , and those at depth $d + 1$ are the children of the internal vertices at depth $d$ , so $K = 2^d + \#\{\text{internal vertices at depth } d\}$ . At least one vertex at depth $d$ is a leaf, so $2^d \leqslant K < 2^{d+1}$ . This determines $d = \lfloor \log_2 K \rfloor$ , and with it the number of leaves at each depth, and every leaf has depth at least $\lfloor \log_2 K \rfloor$ .

Figure 5.8. The exchange. The two deepest sibling leaves

a

b

and their parent

n

swap places with a leaf

c

at least two levels higher;

a

and

b

rise to depth

p' + 1

and

c

falls to depth

p - 1

For example, six leaves can occur at depths $2$ and $3$ . The proposition gives the asymptotic bound: the mean depth of any full binary tree with $K$ leaves is at least $\lfloor \log_2 K \rfloor$ , which is $\Omega(\log K)$ . The exact bound $\log_2 K$ is proved differently.

Theorem 5.33 (Average lower bound for sorting).

Suppose the $n!$ relative orders of $n$ distinct keys are equally likely. Every deterministic comparison sort has mean number of comparisons at least $\log_2(n!)$ , and therefore $\Omega(n \log n)$ .

Discussion.

The proof turns the leaf depths into lengths of intervals. Each leaf is reached by a word of left and right choices, and a word of length $d$ picks out a subinterval of $[0, 1)$ of length $2^{-d}$ by halving repeatedly. Since no leaf’s word begins another leaf’s word, the intervals do not overlap, so their lengths add up to at most $1$ . The mean depth is then bounded below by comparing the arithmetic mean of the numbers $2^{-d_i}$ with their geometric mean. The inequality of the means was proved for two numbers in Lesson 1; the proof extends it to $K$ numbers by doubling up to a power of two and padding.

Proof.

Keep one reachable leaf of the decision tree for each of the $K = n!$ relative orders, and let their depths be $d_1, \ldots, d_K$ ; the mean number of comparisons is $K^{-1}\sum_i d_i$ . Each path from the root to a leaf is a word of left and right choices. No leaf’s word can be a prefix of another leaf’s word, because a computation stops when it reaches a leaf. To a word of length $d_i$ associate the subinterval of $[0, 1)$ of length $2^{-d_i}$ obtained by choosing the left or right half at each successive letter. The intervals for distinct leaf words do not overlap, so their total length is at most $1$ :

\sum_{i=1}^{K} 2^{-d_i} \leqslant 1 .

Write $x_i = 2^{-d_i} > 0$ and $A = K^{-1}\sum_i x_i$ , so that $A \leqslant 1/K$ . We need the inequality of arithmetic and geometric means for $K$ positive numbers, $\bigl(\prod_i x_i\bigr)^{1/K} \leqslant A$ . For two numbers $u, v$ it is $\sqrt{uv} \leqslant (u + v)/2$ . For a list of $2^r$ numbers, split it into two equal halves with geometric means $G_1, G_2$ and arithmetic means $A_1, A_2$ ; by induction on $r$ , $G_1 \leqslant A_1$ and $G_2 \leqslant A_2$ , so the whole list has geometric mean $\sqrt{G_1 G_2} \leqslant \sqrt{A_1 A_2} \leqslant (A_1 + A_2)/2$ , its arithmetic mean. For general $K$ , choose a power of two $N \geqslant K$ and append $N - K$ copies of $A$ to the list $x_1, \ldots, x_K$ . The enlarged list still has arithmetic mean $A$ , so the power-of-two case gives $\bigl(\prod_i x_i\bigr) A^{N-K} \leqslant A^N$ , and cancelling the positive factor $A^{N-K}$ gives $\prod_i x_i \leqslant A^K$ .

Substituting $x_i = 2^{-d_i}$ ,

2^{-\frac{1}{K}\sum_i d_i} \leqslant A \leqslant \frac{1}{K} .

Taking base-two logarithms and multiplying by $-1$ , which reverses the inequality, gives $K^{-1}\sum_i d_i \geqslant \log_2 K = \log_2(n!)$ . Finally $\log_2(n!) \geqslant \lfloor n/2 \rfloor \log_2(n/2) = \Omega(n \log n)$ , as in the worst-case bound.

Example 5.34 (Six outcomes).

With six equally likely outcomes, a full binary tree may have two leaves at depth $2$ and four at depth $3$ . Its mean depth is $(2 \cdot 2 + 4 \cdot 3)/6 = 8/3$ , which is at least $\log_2 6 \approx 2.585$ . The same leaf-depth argument applies to the $n!$ possible input orders.

Sorting algorithms that are faster than $n \log n$ exist, such as counting sort and radix sort, but only because they use information about the keys beyond pairwise comparison, for instance that they are small integers usable as array indices.

Problem 5.14.

Draw a decision tree for insertion sort on three distinct keys $a_0, a_1, a_2$ , and give its height and the mean depth of its leaves. Compare both with $\lceil \log_2 3! \rceil$ and $\log_2 3!$ .

Problem 5.15.

Show that five distinct keys can be sorted with $7$ comparisons in the worst case, and that no comparison sort does it with $6$ .

Sorted Arrays as Sets

A sorted array implements the set interface. Building it is sorting, $O(n \log n)$ by merge sort. find(k) is binary search, $O(\log n)$ . The smallest and largest keys are at the two ends, and find_next(k) and find_prev(k) are binary searches for the position where $k$ would go. Inserting or deleting while keeping the order shifts up to $n$ items.

Data structure	`build(X)`	`find(k)`	`insert(x)`, `delete(k)`	`find_min()`, `find_max()`	`find_prev(k)`, `find_next(k)`
Array	$n$	$n$	$n$	$n$	$n$
Sorted array	$n \log n$	$\log n$	$n$	$1$	$\log n$
Direct access array	$u$	$1$	$1$	$u$	$u$
Hash table	$n$ (e)	$1$ (e)	$1$ (a)(e)	$n$	$n$

Each entry is an $O(\cdot)$ bound; (e) marks an expected bound and (a) an amortized one. For the sorted array, find is optimal among comparison algorithms by the lower bound for searching, and the bound does not apply to the hash table, which is not a comparison algorithm.

Problem 5.16.

Implement the set interface on a sorted array as a class Sorted_Array_Set, using merge_sort in build and binary search in find, find_next and find_prev, with the running times of the table.

Exercises on Connectivity and Trees

Exercise 5.1.

How many spanning subgraphs of $K_4$ are trees?

Exercise 5.2.

Prove that every connected graph with at least two vertices has a vertex that is not an articulation vertex.

Exercise 5.3.

Let $n \geqslant 2$ , and let $d_1 \leqslant d_2 \leqslant \cdots \leqslant d_n$ be integers. Show that there is a tree with vertex degrees $d_1, \ldots, d_n$ if and only if $d_1 \geqslant 1$ and $\sum_i d_i = 2n - 2$ .

Exercise 5.4.

Let $T_1, \ldots, T_k$ be subtrees of a tree $T$ , meaning subgraphs that are trees, any two of which have at least one vertex in common. Prove that some vertex lies in every $T_i$ .

Exercise 5.5.

The radius of a connected graph is $\min_{v} \max_{w} d(v, w)$ , the least over all vertices $v$ of the greatest distance from $v$ to another vertex. Let $C_n$ be the cycle on $n$ vertices, with vertices $1, \ldots, n$ and edges $\{i, i+1\}$ and $\{n, 1\}$ . Find the radius and the diameter of $K_6$ , of $C_9$ and of $K_{5,7}$ .

Exercise 5.6.

A directed graph $G$ has $1000$ vertices. Its underlying undirected graph has one connected component of size $700$ , and $G$ has one strongly connected component of size $500$ ; its other strongly connected components are smaller.

Suppose $650$ vertices are reachable from a vertex $u$ . Is $u$ in the component of size $700$ ? Explain.
Is $u$ in the strongly connected component of size $500$ ? Explain.
Suppose $600$ vertices are reachable from a vertex $v$ , and $600$ vertices are reachable from $v$ once every arc is reversed. Is $v$ in the strongly connected component of size $500$ ? Explain.
Prove that for every vertex $w$ of the component of size $700$ , there is a directed walk from $v$ to $w$ or one from $w$ to $v$ .

Exercise 5.7.

The divisibility graph $D(n)$ has vertices $1, 2, \ldots, n$ and an edge between $i \neq j$ whenever one of them divides the other.

Draw $D(12)$ . How many connected components does it have, and what is the size of its largest clique?
Prove that for every $d \geqslant 2$ , a graph with no loops in which every vertex has degree at least $d$ contains a simple cycle through at least $d + 1$ vertices.

Exercises on Searching

Exercise 5.8.

A narrow island runs north–south for $n$ kilometres, and a searcher must locate a friend to the nearest kilometre. A tracking device tells the searcher whether the friend is north or south of the current position, but not how far, and a teleporter jumps to any given kilometre in constant time. If the friend is $k$ kilometres from the nearer end of the island, at kilometre $k$ or $n - k$ , describe an algorithm that finds the friend after visiting $O(\log k)$ locations.

Exercise 5.9.

A ridge is given as an array of $n$ distinct altitudes. A point is a good collection point if it is lower than all its neighbours in the array. Design an algorithm running in $O(\log n)$ time that finds a good collection point, prove it correct, and prove its running time.

Exercises on Sorting

Exercise 5.10.

Implementations of insertion sort and merge sort run on the same machine. On inputs of size $n$ , insertion sort takes $8n^2$ steps and merge sort takes $64\, n \log_2 n$ steps. For which values of $n$ does insertion sort beat merge sort?

Exercise 5.11.

Person $i$ , for $i \in \{1, \ldots, n\}$ , enters a room at time $a_i$ and leaves at time $b_i > a_i$ , all the $a_i, b_i$ being distinct. The lights are off at the start of the day; the first person to enter switches them on, and a person who leaves an empty room switches them off. Given $(a_1, b_1), \ldots, (a_n, b_n)$ , we want the number of times the lights are switched on. Design, and prove correct and costed,

a $\Theta(n^2)$ algorithm, and
an $O(n \log n)$ algorithm.

Exercise 5.12.

For each scenario choose selection sort, insertion sort or merge sort, and justify the choice by asymptotic running time.

A data structure $D$ maintains an extrinsic order on $n$ items, with D.get_at(i) in worst-case $\Theta(1)$ time and D.set_at(i, x) in worst-case $\Theta(n \log n)$ time. Sort the items of $D$ in place.
A static array holds references to $n$ comparable objects, any two of which take $\Theta(\log n)$ time to compare. Sort the references so that the objects appear in nondecreasing order.
A sorted array of $n$ integers, each fitting in a machine word, has had $\log \log n$ exchanges made between pairs of adjacent items. Re-sort it.

Exercise 5.13.

Describe the principle of merge sort, and show the steps it takes to sort the array $(9, 3, 6, 2, 4, 1, 5)$ .
Insertion sort can be seen as a merge sort in which each step splits an array of size $n$ into one of size $1$ , the element to be inserted, and one of size $n - 1$ . By solving the appropriate recurrence, show that this recursive insertion sort takes $O(n^2)$ time, assuming that merging two arrays takes $O(n)$ time.
Show that merge sort on a linked list takes $O(n \log n)$ time, and that it can be done with $O(1)$ auxiliary space apart from the recursion, showing how. A programmer who can merge arrays only with $O(n)$ extra space proposes to convert arrays to linked lists before sorting them, to save space. Comment on this strategy.

Exercise 5.14.

Suppose that quicksort always partitions into two parts of relative sizes $\alpha$ and $1 - \alpha$ , for a constant $0 < \alpha < \tfrac12$ . Ignoring rounding, find the least depth of a leaf in the recursion tree as a function of $n$ and $\alpha$ .
How long does the quicksort of these notes take if all the keys are equal? Explain.
What are the advantages and disadvantages of choosing the pivot at random? How does it affect the worst-case and the average-case running time?

Exercise 5.15.

How would you construct an input that makes randomized quicksort take quadratic time, without access to the state of the random number generator?

Exercise 5.16.

Merge sort can be implemented as the usual two-way merge sort, or as a three-way merge sort that splits its input into three and sorts each part recursively.

Find the worst-case number of comparisons needed to merge two sorted arrays of length $n/2$ .
Find the worst-case number of comparisons needed to merge three sorted arrays of length $n/3$ , both by merging all three at once and by merging in pairs.
Using these, and solving suitable recurrences, find the total number of comparisons made by two-way and by three-way merge sort.
If comparisons dominate the cost, which would you expect to be faster on an arbitrary array?

Exercise 5.17.

Describe an algorithm, running in time strictly better than $O(n^2)$ , that takes a positive integer $s$ and a set $A$ of $n$ positive integers and decides whether two distinct elements of $A$ add up to exactly $s$ . Give its running time.

Exercise 5.18.

Each of $n$ computers has run the same computation, and we want to know whether strictly more than $n/2$ of them arrived at the same result. The only available query takes two computers and reports whether they produced the same result. Design an algorithm that decides this with $O(n \log n)$ queries, prove it correct, and prove the bound on the number of queries.

Exercise 5.19.

Find an asymptotically tight upper bound for the recurrence $T(1) = 1$ , $T(n) = T(n-1) + \log_2 n$ , and explain your answer.

Check Yourself

Fresh questions on the whole lesson — none of them is worked out above. Work each one out on paper before opening Python; the box only tells you whether you got there.

Answers are checked in your browser, as often as you like. Nothing is sent anywhere and nothing is kept but your own work. A formula may be written with the symbols themselves or with ~ & | -> <-> ^, and \and, \or, \to expand as you type.