Chapter 1: Analysis of Algorithms

Exercise 1.1

Both $f(N)$ and $N \lg N$ are strictly positive as $N \to \infty$. For sufficiently large $N$, the $\lg N$ term dominates the constant hidden in $O(N)$. Therefore,

$$\lim_{N \to \infty} \frac{f(N)}{N \lg N}=1+\frac{O(N)}{N \lg N}=1,$$

meaning that $0<1-\epsilon < f(N)/(N \lg N) <1+\epsilon$ for an arbitrarily small constant $\epsilon>0$. This trivially implies $f(N)=\Theta(N\log N)$.

It would be a mistake to set the lower bound to 1, since the book's definition of big-O allows negative functions, too.

Exercise 1.2

The book already mentions that there are various strategies to avoid sentinels. For example, on the Algorithms, 4th Edition by RS, KW book’s website, you can find an interesting approach (see the section Creative Problems), that uses a single auxiliary array aux[]. As stated there: "The merge procedure copies the second half of a[] to aux[] in decreasing order and then does the merge back to a[]." This improves performance by eschewing boundary checks on indices. Nonetheless, such a mergesort isn’t stable anymore, which is a key property of this sorting algorithm.

On the same website, you have Merge.java; a standard implementation of the top-down mergesort algorithm without relying on a boundary value. As a bonus, it also offers index-based (indirect) sorting, which avoids moving array elements around.

Exercise 1.3

GeeksforGeeks covers 3-way mergesort in great detail.

Below is the driver code to measure execution time. Replace the original driver code in programs from GeeksforGeeks implementing standard and 3-way mergesort algorithms.

if __name__ == "__main__":
    import random
    import time

    TRIALS = 10
    N = 500_000
    times = []

    for trial in range(1, TRIALS + 1):
        print(f"Trial {trial}/{TRIALS}: generating random list of {N} integers...")
        a = [random.randint(0, 10**9) for _ in range(N)]

        print(f"Trial {trial}: starting...")
        t0 = time.perf_counter()
        # Change this line to call a different target function.
        three_way_merge_sort(a, 0, len(a) - 1)
        t1 = time.perf_counter()
        elapsed = t1 - t0
        times.append(elapsed)
        print(f"Trial {trial} finished in {elapsed:.3f} seconds.")

    avg = sum(times) / len(times)
    print(f"\nRan {len(times)} successful trials. Average: {avg:.3f}s, Min: {min(times):.3f}s, Max: {max(times):.3f}s")

Here are the outputs created on a MacBook Pro 2019 machine:

--- standard mergesort ---
Ran 10 successful trials. Average: 1.980s, Min: 1.895s, Max: 2.055s

--- 3-way mergesort ---
Ran 10 successful trials. Average: 1.931s, Min: 1.887s, Max: 2.014s

3-way mergesort has a lower recursion depth, which may potentially improve performance. The k-way merge is a generalization of this idea.

Exercise 1.4

Recurrence (1) from the book gives

$$C_{N+1}-C_N=C_{\lceil (N+1)/2 \rceil}+C_{\lfloor (N+1)/2 \rfloor}+(N+1)-C_{\lceil N/2 \rceil}-C_{\lfloor N/2 \rfloor}-N.$$

Since $\lfloor (N+1)/2 \rfloor=\lceil N/2 \rceil$ and $\lceil (N+1)/2 \rceil=\lfloor N/2 \rfloor +1$ it follows that

$$C_{N+1}-C_N=C_{\lfloor N/2 \rfloor +1}-C_{\lfloor N/2 \rfloor}+1.$$

The quantity $\lfloor N/2 \rfloor$ is a positive integer, so apply recursively the above expansion by leveraging a useful property of floor and ceiling functions that $\lfloor\lfloor x\rfloor/2 \rfloor=\lfloor x/2 \rfloor$. Carry out this process until the problem size drops to 1, recalling that $C_1=0$. Thus,

$$\begin{align*} C_{N+1}-C_N &= C_{\lfloor N/2 \rfloor +1}-C_{\lfloor N/2 \rfloor}+1 \\ &= C_{\lfloor N/4 \rfloor +1}-C_{\lfloor N/4 \rfloor}+1+1 \\ &\dots \\ &=C_2-C_1+\underbrace{1+1+\dots+1}_{\lfloor \lg N \rfloor} \\ &= 2+\lfloor \lg N \rfloor. \end{align*}$$

---

Express $C_N$ as a sum of differences

$$\begin{align*} C_N &= (C_N-C_{N-1})+ (C_{N-1} - C_{N-2}) + \dots+ (C_2-C_1) \\ &=(2+\lfloor\lg (N-1)\rfloor)+(2+\lfloor\lg (N-2)\rfloor)+\dots+(2+\lfloor\lg 1\rfloor) \\ &=\sum_{1 \le k <N} (\lfloor\lg k\rfloor+2). \end{align*}$$

Exercise 1.5

As mentioned in the book, the theorem for a general $N$ follows from (1) by induction. Use the equation $C_N=N \lceil \lg N \rceil+N-2^{\lceil \lg N \rceil}$ as the inductive hypothesis. The base case $C_1=0$ trivially holds, since $\lg 1=0$. For $N>1$ (the inductive step)

$$\begin{align*} C_N&=\lceil N/2 \rceil \lceil \lg {\lceil N/2 \rceil} \rceil+\lceil N/2 \rceil-2^{\lceil \lg {\lceil N/2 \rceil} \rceil} \\ &\hspace{1cm} + \lfloor N/2 \rfloor \lceil \lg {\lfloor N/2 \rfloor} \rceil+\lfloor N/2 \rfloor-2^{\lceil \lg {\lfloor N/2 \rfloor} \rceil} && \text{(by the inductive hypothesis)} \\ &\hspace{1cm} +N \\ &= \lceil N/2 \rceil \lceil \lg {\lceil N/2 \rceil} \rceil+\lfloor N/2 \rfloor \lceil \lg {\lfloor N/2 \rfloor} \rceil+2N-2^{\lceil \lg {\lceil N/2 \rceil} \rceil}-2^{\lceil \lg {\lfloor N/2 \rfloor} \rceil} && \text{($N=\lceil N/2 \rceil+\lfloor N/2 \rfloor$)}. \end{align*}$$

---

If $N$ is even, then $\lceil N/2 \rceil=\lfloor N/2 \rfloor=N/2$, so the last line simplifies to

$$\begin{align*} C_N&=2 \cdot (N/2) \lceil \lg {(N/2)} \rceil+2N- 2\cdot 2^{\lceil \lg {(N/2) } \rceil} \\ &=N \lceil \lg N \rceil-N+2N-2^{\lceil \lg N \rceil} && \text{($\lceil \lg {(N/2)} \rceil=\lceil \lg N-1 \rceil=\lceil \lg N \rceil-1$)} \\ &=N \lceil \lg N \rceil+N-2^{\lceil \lg N \rceil}. \qquad \checkmark \end{align*}$$

---

If $N$ is odd, then $\lceil N/2 \rceil=(N+1)/2$ and $\lfloor N/2 \rfloor=(N-1)/2$, so

$$\begin{align*} C_N&=\frac{N+1}{2} \bigg\lceil \lg \frac{N+1}{2} \bigg\rceil+\frac{N-1}{2} \bigg\lceil \lg \frac{N-1}{2} \bigg\rceil+2N-2^{\big\lceil \lg \frac{N+1}{2} \big\rceil}-2^{\big\lceil \lg \frac{N-1}{2} \big\rceil} \\[0.4cm] &=\frac{N+1}{2} \lceil \lg (N+1) \rceil + \frac{N-1}{2} \lceil \lg (N-1) \rceil-N+2N-2^{\lceil \lg (N+1) \rceil-1}-2^{\lceil \lg (N-1) \rceil-1} \\[0.4cm] &=\frac{N+1}{2} \lceil \lg (N+1) \rceil + \frac{N-1}{2} \lceil \lg (N-1) \rceil+N-2^{\lceil \lg (N +1)\rceil-1}-2^{\lceil \lg (N-1) \rceil-1}. \end{align*}$$

We must figure out how to express $\lceil \lg (N+1) \rceil$ and $\lceil \lg (N-1) \rceil$. We know that $N \in (2^k,2^{k+1})$ for some positive integer $k$. Observe that$\lceil \lg (N+1) \rceil=\lceil \lg N\rceil=k+1$. If $N>2^k+1$ then$\lceil \lg (N-1) \rceil=\lceil \lg N \rceil=k+1$, otherwise $\lceil \lg (N-1) \rceil=\lceil \lg N \rceil-1=k$. Therefore, we must differentiate these two sub-cases.

When $N>2^k+1$

$$\begin{align*} C_N &=\frac{N+1}{2} \lceil \lg N \rceil + \frac{N-1}{2} \lceil \lg N \rceil+N-2^{\lceil \lg N \rceil-1}-2^{\lceil \lg N \rceil-1} \\ &=N \lceil \lg N \rceil +N-2 \cdot 2^{\lceil \lg N \rceil-1} \\ &= N \lceil \lg N \rceil +N-2^{\lceil \lg N \rceil}. \qquad \checkmark \end{align*}$$

If $N=2^k+1$ then $(N-1)/2=(2^k+1-1)/2=2^{k-1}=2^{\lceil \lg N \rceil-2}$. Thus,

$$\begin{align*} C_N &=\frac{N+1}{2} \lceil \lg N \rceil + \frac{N-1}{2} \lceil \lg N \rceil-2^{\lceil \lg N \rceil-2}+N-2^{\lceil \lg N \rceil-1}-2^{\lceil \lg N \rceil-2} \\ &=N \lceil \lg N \rceil +N-2^{\lceil \lg N \rceil-1}-2 \cdot 2^{\lceil \lg N \rceil-2} \\ &=N \lceil \lg N \rceil +N-2 \cdot 2^{\lceil \lg N \rceil-1} \\ &=N \lceil \lg N \rceil +N-2^{\lceil \lg N \rceil}. \qquad \checkmark \end{align*}$$

---

This concludes the proof that the inductive hypothesis is true for all $N \ge1$.

Exercise 1.6

Use the following three-way merge procedure in Java instead of the original from Exercise 1.3. It uses sentinels, like Program 1.1 from the book, so counting the number of comparisons inside the loop is straightforward.

static void merge(int arr[], int left, int mid1, int mid2, int right) {  
    // Sizes of three subarrays
    int size1 = mid1 - left + 1;
    int size2 = mid2 - mid1;
    int size3 = right - mid2;
        
    // Temporary arrays for three parts
    int[] leftArr = new int[size1 + 1];
    int[] midArr = new int[size2 + 1];
    int[] rightArr = new int[size3 + 1];
        
    // Copy data to temporary arrays
    for (int i = 0; i < size1; i++) {
        leftArr[i] = arr[left + i];
    }
    for (int i = 0; i < size2; i++) {
        midArr[i] = arr[mid1 + 1 + i];
    }
    for (int i = 0; i < size3; i++) {
        rightArr[i] = arr[mid2 + 1 + i];
    }
      
    // Add sentinels
    leftArr[size1] = INFTY;
    midArr[size2] = INFTY;
    rightArr[size3] = INFTY;
        
    // Merge three sorted subarrays
    for (int index = left, i = 0, j = 0, k = 0; index <= right; index++) {
        // Find the smallest among the three current elements
        // and place it into the merged array
        if (leftArr[i] <= midArr[j]) {
            if (leftArr[i] <= rightArr[k]) {
                arr[index] = leftArr[i++];	
            } else {
                arr[index] = rightArr[k++];
            }
        } else if (midArr[j] <= rightArr[k]) {
            arr[index] = midArr[j++];
        } else {
            arr[index] = rightArr[k++];
        }
    }
}

Each iteration of the main for loop performs 2 comparisons to decipher the minimum among the 3 candidates. The recurrence is

$$C_N=3C_{N/3 }+2N \space\space \text{for $N > 1$ with $C_1=C_0=0$.}$$

Consider the case when $N$ is a power of 3, and use the same analysis as in the book for the standard mergesort, to get $C_N=2N\log_3 N$.

Exercise 1.7 🌟

Algorithm science is a methodology for developing machine-independent falsifiable hypotheses. This exercise is about the doubling hypothesis.

According to Exercise 1.1, $t_N=cN \lg N+dN \sim cN \lg N$. Estimate $t_{2N}$, independent of the machine, as follows:

$$\begin{align*} t_{2N} &\sim 2cN\lg {2N} \\ &=2cN+2cN\lg N \\ &\sim 2cN+2t_N \\ &\sim 2t_N(1+1/\lg N) && \text{($cN\sim t_N/\lg N$)}. \end{align*}$$

The next Python script shows how well the estimated $t_{2N}$ reflects the "actual" $t_{2N}$. Run different experiments by altering the "machine-dependent" constants $c$ and $d$.

from math import log

# Machine dependent constants in the simulation.
c = 3.5
d = 7.1

def t(n):
    return c * n * log(n, 2) + d * n

def estimate_t_2n(t_n, n):
    return 2 * t_n * (1 + 1 / log(n, 2))

for n in [10, 100, 1000, 10000]:
    t_n = t(n)
    est_t_2n = estimate_t_2n(t_n, n)
    act_t_2n = t(2 * n)
    print(f"n: {n:6},\tEstimated: {est_t_2n:10.2f},\tActual: {act_t_2n:10.2f},\tRel. Error: {abs(est_t_2n - act_t_2n) / act_t_2n:.2%}")

The output shows that the relative error drops quickly as $N$ increases.

n:     10,	Estimated:     487.28,	Actual:     444.53,	Rel. Error: 9.62%
n:    100,	Estimated:    6984.43,	Actual:    6770.70,	Rel. Error: 3.16%
n:   1000,	Estimated:   92385.37,	Actual:   90960.49,	Rel. Error: 1.57%
n:  10000,	Estimated: 1152826.43,	Actual: 1142139.87,	Rel. Error: 0.94%

Exercise 1.8

Use the Python implementation of mergesort from GeeksforGeeks and replace the driver code with the following snippet:

import time
from math import log
from random import randint

if __name__ == "__main__":
    for n in (1_000_000, 10_000_000):
        arr = [randint(0, 100) for _ in range(n)]

        start_time = time.time()
        mergeSort(arr, 0, len(arr) - 1)
        end_time = time.time()
        t_n = end_time - start_time

        if n == 1_000_000:
            print(f"Actual 1x time: {t_n:.2f} seconds")
            t10x_estimate = 10 * t_n * (1 + log(10, 2) / log(n, 2))
            print(f"Estimated 10x time: {t10x_estimate:.2f} seconds")
        else:
            print(f"Actual 10x time: {t_n:.2f} seconds")
            print(f"Relative Error: {abs(t_n - t10x_estimate) / t_n:.2%}")

Here’s an output on a MacBook Pro 2019:

Actual 1x time: 4.05 seconds
Estimated 10x time: 47.20 seconds
Actual 10x time: 45.84 seconds
Relative Error: 2.97%

Exercise 1.9

See Sort2distinct.java.

The inline comment of the sort method says that it assumes the input has at most 3 distinct values. Without any preprocessing, this should be 2 (see also the next exercise).

Exercise 1.10

Perform an initial linear scan to record one set of indices $i$, $j$ and $k$ for those three distinct values. Determine the index of the median and exchange it with an element at the beginning of an array. Finally, run the 3-way partitioning procedure sort from the previous exercise.

As an additional practice, solve the LeetCode problem Sort Colors.

Exercise 1.11

The following Python program implements this concept. The merge procedure uses sentinels to be aligned with the version from the book.

def merge(a, left, mid, right):
    global c_n # Global counter for number of comparisons

    n1 = mid - left + 1
    n2 = right - mid

    # Create temp arrays
    b = [0] * n1
    c = [0] * n2

    # Copy data to temp arrays b[] and c[]
    for i in range(n1):
        b[i] = a[left + i]
    for j in range(n2):
        c[j] = a[mid + 1 + j]

    # Add sentinels
    b.append(float('inf'))
    c.append(float('inf'))

    # Merge the temp arrays back into a[left..right]
    i = j = 0
    for k in range(left, right + 1):
        c_n += 1 # Simulate profiling by counting comparisons
        if b[i] <= c[j]:
            a[k] = b[i]
            i += 1
        else:
            a[k] = c[j]
            j += 1

def merge_sort(a, left, right):
    if left < right:
        mid = (left + right) // 2
        merge_sort(a, left, mid)
        merge_sort(a, mid + 1, right)
        merge(a, left, mid, right)

if __name__ == "__main__":
    import time
    import random

    print(f"{'n':>10} {'t(n)':>13} {'c(n)':>14} {'t(n)/c(n)':>10}")
    print("-" * 51)
    n = 1
    for _ in range(8):
        n *= 10
        a = [random.randint(0, 10**9) for _ in range(n)]

        start_time = time.time()
        c_n = 0 # Reset comparison counter
        merge_sort(a, 0, len(a) - 1)
        end_time = time.time()
        t_n = (end_time - start_time) * 1_000_000
        print(f"{n:>10} {t_n:>13.2f} {c_n:>14.2f} {t_n / c_n:>10.2f}")

The running time is shown in microseconds. The ratio $t_N/c_N$ stabilizes, as the problem size increases, although there are some fluctuations. Here is the output generated on a MacBook Air 2025 computer:

         n          t(n)           c(n)  t(n)/c(n)
---------------------------------------------------
        10        122.07          34.00       3.59
       100        791.07         672.00       1.18
      1000       5255.94        9976.00       0.53
     10000      37181.85      133616.00       0.28
    100000     233823.30     1668928.00       0.14
   1000000    2852994.92    19951424.00       0.14
  10000000   35313109.64   233222784.00       0.15
 100000000  476664655.92  2665782272.00       0.18

On a MacBook Pro 2019 machine, the constant approached $0.3$.

Exercise 1.12

Let $T_N$ denote the total number of compares used by quicksort on all $N!$ permutations of $N$ elements. The average number of compares is $C_N=T_N/N!$, so the base cases are $T_2=5$ (see errata about Theorem 1.3) and $T_1=T_0=0$. The recurrence for $T_N$ follows from the simplified recurrence for $C_N$

$$\begin{align*} NC_N&=(N+1)C_{N-1}+2N \\[0.2cm] N\left(\frac{T_N}{N!}\right) &= (N+1)\left(\frac{T_{N-1}}{(N-1)!}\right)+2N \\[0.4cm] \frac{T_N}{(N-1)!} &= (N+1)\frac{T_{N-1}}{(N-1)!}+2N \\[0.4cm] &\therefore T_N = (N+1)T_{N-1}+2N! \qquad \text{for $N>2$}. \end{align*}$$

Exercise 1.13 🌟

The invariant that the subarrays left after partitioning a random permutation are themselves both random permutations is quintessential both for analysis and performance guarantees. Observe that Program 1.2 only moves the partitioning element (pivot) $v$ to its final position at the end. Leaving the pivot out of the partitioning process is crucial to ensure that the invariant remains true during the whole process.

The proof below is adopted from Sedgewick’s PhD thesis.

Suppose that a permutation of $\{1,2,\dots,N\}$ is being partitioned with all such $N!$ permutations equally likely. Choose a pivot $1 \le v \le N$, so that after partitioning the size of the left subarray becomes $v-1$. Any rearrangement of these $v-1$ elements, out of the possible $(v-1)!$, in the original permutation is mapped to a unique permutation in the left subarray. In other words, we can establish a bijection between these two objects. Since all the original permutations are equally likely, the same is true for permutations in the left subarray. The analogous reasoning applies, independently, for the right subarray. This concludes the proof.

Moving the pivot during the partitioning process, by setting $j:=hi+1$, introduces bias into the subarrays (unless the pivot already happens to be in its final position). The probability of having a permutation where the pivot remains in its initial position is quite low. In our case, the first element from the left larger than the pivot will trigger it to move; it tends to fall near the beginning of the left subarray. Therefore, not all positions are equally likely to contain $v$.

Exercise 1.14 🌟

This exercise showcases a technique to eliminate dependence on historical data on the RHS of the recurrence relation.

$$\begin{align*} A_N&=1+\frac{2}{N}\sum_{1\le j \le N}A_{j-1} && \text{(for $N>0$)} \\ NA_N-(N-1)A_{N-1}&=1+2A_{N-1} && \text{(for $N>1$, after eliminating summation)} \\ NA_N&=(N+1)A_{N-1}+1 \\ \frac{A_N}{N+1}&=\frac{A_{N-1}}{N}+\frac{1}{(N+1)N} && \text{(after dividing both sides with $N(N+1)$)} \\ \frac{A_N+1}{N+1}&=\frac{A_{N-1}+1}{N} && \text{$\left(\frac{1}{(N+1)N}=\frac{1}{N}-\frac{1}{N+1}\right)$} \\ \frac{A_N+1}{N+1}&=\frac{A_{N-1}+1}{N}=\dots=\frac{A_1+1}{2} && \text{(iterating)} \\ &\therefore \boxed{A_N=N}. \end{align*}$$

Exercise 1.15 🌟

The derivation augments the technique from the book by introducing an extra dimension. Finding the average number of exchanges used during the first partitioning stage (before the pointers cross) is a harder task than deriving $C_N$ or $A_N$. We’ve dependencies on both the pivot and arrangement of keys (values to sort).

The proof is adopted from Sedgewick’s PhD thesis.

WLOG assume that the input array is a random permutation of the set $\{1,2,\dots,N\}$. The base cases are $B_1=B_0=0$ and the recurrence is

$$\begin{align*} B_N=&\frac{1}{N}\sum_{1 \le v\le N} \bigg\{\text{average number of exchanges when the pivot is $v$}\bigg \} \\ &+\frac{2}{N}\sum_{1\le j \le N}B_{j-1} && \text{(for $N>1$)}. \end{align*}$$

Let’s analyze the first term of the sum by looking at Program 1.2 from the book. Quicksort is parsimonious regarding exchanges; only those elements are swapped that must be swapped. If the pivot is $v=a[N]$, then only those keys among $a[v],\dots,a[N-1]$ which are smaller than $v$ are exchanged into the right subarray. Furthermore, each element is exchanged at most once during the whole partitioning process. Let $X_v$ be the random variable denoting the number of exchanges used during the first partitioning stage when the pivot is $v$. The probability mass function of $X_v$ is given by

$$\Pr\{X_v=k\}=\frac{\dbinom{N-v}{N-v-k}\dbinom{v-1}{k}}{\dbinom{N-1}{N-v}}=\frac{\dbinom{N-v}{k}\dbinom{v-1}{v-1-k}}{\dbinom{N-1}{v-1}}.$$

The numerator expresses the number of ways to select $k$ smaller elements from the left subarray and use them to form the right subarray. The denominator is just the total number of possible combinations to form the right subarray. As a side note, the right side of the equation follows from the identity $\binom{n}{n}=\binom{n}{n-k}$ and shows symmetry in the problem, i.e., it describes the case when the first element is chosen as the pivot. At any rate, $k \in [0,v-1]$.

The average number of exchanges is the expectation of $X_v$

$$\begin{align*} \mathbb{E}{[X_v]} &= \sum_{k=0}^{v-1} k\Pr\{X_v=k\} \\[0.5cm] &= \sum_{k=1}^{v-1} {k \cdot \frac{\dbinom{N-v}{k}\dbinom{v-1}{v-1-k}}{\dbinom{N-1}{v-1}} }\\[0.8cm] &= \frac{N-v}{\dbinom{N-1}{v-1}} \sum_{k=1}^{v-1} \binom{N-v-1}{k-1}\binom{v-1}{v-1-k} \\[0.8cm] &= \frac{N-v}{\dbinom{N-1}{v-1}} \sum_{k=0}^{v-2} \binom{N-v-1}{k}\binom{v-1}{v-2-k} \\[0.8cm] &= \frac{N-v}{\dbinom{N-1}{v-1}} \binom{N-2}{v-2} && \text{(Vandermonde’s convolution)} \\[0.8cm] &= \frac{(N-v)(v-1)}{N-1}. \end{align*}$$

This gives

$$\begin{align*} B_N=&\frac{1}{N}\sum_{1 \le v\le N} \mathbb{E}{[X_v]}+\frac{2}{N}\sum_{1\le j \le N}B_{j-1} \\ =&\frac{1}{N(N-1)}\sum_{1 \le v\le N} (N-v)(v-1)+\frac{2}{N}\sum_{1\le j \le N}B_{j-1} \\ &= \frac{1}{N(N-1)}\binom{N}{3}+\frac{2}{N}\sum_{1\le j \le N}B_{j-1} \\ &= \bold{\frac{N-2}{6}}+\frac{2}{N}\sum_{1\le j \le N}B_{j-1}. \end{align*}$$

If we take into account the official errata, then $B_N \neq \frac{1}{6}C_N-\frac{1}{2}A_N.$ Namely, the equation holds only if we assume that the average partitioning cost in $C_N$ is $N+1$ instead of $N+1-1/N$.

Exercise 1.16 🌟

This exercise demonstrates the significance of algorithm analysis. Having an analytical expression for the average number of small subarrays encountered during sorting can facilitate performance optimization.

Let $B_{Nk}$ denote the number of subarrays of size $k>0$ encountered, on the average, when sorting a random array of size $N$ with quicksort. There are 3 cases:

1. Base case 1: if $N<k$ then we can’t have a subarray of size $k$, so $B_{Nk}=0$.

2. Base case 2: if $N=k$ then $B_{Nk}=1$, since only the initial array is of size $k$.

3. Recursive case: if $N>k$ then the initial call is on a subarray whose size is larger than $k$, hence we don’t count it. The recurrence reduces to

$$B_{Nk}=\frac{2}{N}\sum_{0\le j < N}B_{jk}.$$

Fast forward the exact same steps as in Exercise 1.14 to get

$$\frac{B_{Nk}}{N+1}=\frac{B_{(N-1)k}}{N}=\dots=\frac{B_{(k+1)k}}{k+2} \space\space\space\space \text{(for $N>k+1$)}.$$

We can’t iterate further than $B_{(k+1)k}$, but the main recurrence gives $B_{(k+1)k}=2/(k+1)$; all base cases are 0s except $B_{kk}=1$. Therefore,

$$B_{Nk}=\frac{2(N+1)}{(k+1)(k+2)}\space\space\space\space \text{(for $N>k$)}.$$

A simple variation of this problem is the review question Q1.3; the answer is

$B_{Nk}=\cfrac{k(N+1)}{k+2}\qquad \text{(for $N>k$)}.$

Exercise 1.17 🌟

This exercise illustrates the methodology of employing analysis of algorithms in tuning parameters to attain better performance.

Fast forward the exact same steps as in the proof of Theorem 1.3 to get

$$\begin{align*} \frac{C_N}{N+1}&=\frac{C_{M+1}}{M+2}+2\sum_{M+3 \le k \le N+1} \frac{1}{k} && \text{(for $N>M+1$)}\\ &=\frac{C_{M+1}}{M+2}+2(H_{N+1}-H_{M+2}). \end{align*}$$

Calculate $C_{M+1}$ using the main recurrence

$$\begin{align*} C_{M+1} &= (M+1)+1+\frac{2}{M+1}\sum_{1 \le j \le M+1} C_{j-1} \\ &= M+2+\frac{2}{M+1}\sum_{0 \le j \le M} \frac{j(j-1)}{4} && \text{(reindexing and substituting $C_j$)} \\ &= M+2+\frac{1}{2(M+1)}\sum_{1 \le j \le M} j(j-1) \\ &= M+2+\frac{1}{2(M+1)}\left(\frac{M(M+1)(2M+1)}{6}-\frac{M(M+1)}{2}\right) \\ &= M+2+\frac{M(M-1)}{6}. \end{align*}$$

The formula for the average number of compares in quicksort, when using insertion sort to handle small subarrays, is

$$C_N=(N+1)\left(1+\frac{M(M-1)}{6(M+2)}\right)+2(N+1)(H_{N+1}-H_{M+2}) \space\space\space\space \text{(for $N>M$)}.$$

If we take into account the official errata, then the formula changes to

$C_N=(N+1)\left(1-\frac{1}{(M+1)(M+2)}+\frac{M(M-1)}{6(M+2)}\right)+2(N+1)(H_{N+1}-H_{M+2}) \space\space\space\space \text{(for $N>M$)}.$

Exercise 1.18 🌟

This exercise shows a minimization problem in finding the cutoff value for switching to insertion sort.

Ignore small terms (those significantly less than $N$) as well as constant multiples of $N$ (they don’t influence the minimization task), to arrive at the following approximation

$$C_N\approx 2N\ln N +\underset{=f(M)}{\undergroup{\left(\frac{M(M-1)}{6(M+2)}-2\ln {M}\right)}}N.$$

Use a suitable math tool, like WolframAlpha, to solve the minimization problem as well as plot the graph of $f(M)$. Issue plot m(m-1)/(6(m+2))-2ln(m) for 1<=m<60 to see its shape.

Plot of $f(M)$ that shows a global minimum around 12.

Find the minimum by entering m(m-1)/(6(m+2))-2ln(m) minimize for m>1 . It reports a global minimum at $M \approx 12.4$.

You may use a different approximation, like using $\lg (M+2)$ instead of $\lg M$ inside $f(M)$, but the outcome would be similar. Also, you may want to try the more accurate expression for $C_N$ (see the remark in the previous exercise).

Exercise 1.19

According to the graph from the previous exercise, the threshold is $M =49$.

Exercise 1.20

Below is the Python script that reports how many keys in the array of $N=10^4$ random positive integers less than $M=10^6$ are likely to be equal to some other keys in the array.

import random
import math
from collections import Counter
from statistics import mean

def count_colliding_keys(n, m):
    # Generate n random positive integers in [1, m-1].
    arr = [random.randrange(1, m) for _ in range(n)]
    freq = Counter(arr)
    # Count all occurrences of values that appear at least twice.
    return sum(cnt for cnt in freq.values() if cnt >= 2)

def simulate(n=10_000, m=1_000_000, trials=1000, seed=None):
    if seed is not None:
        random.seed(seed)
    results = [count_colliding_keys(n, m) for _ in range(trials)]
    mu = round(mean(results))
    analytic = round(n * (1 - (1 - 1/m) ** (n - 1)))
    print(f"n={n}, m={m}, trials={trials}")
    print(f"simulated mean = {mu}")
    print(f"analytic estimate = {analytic}")

simulate(seed=1)

The output shows an excellent alignment between empirical evidence and analytic result:

n=10000, m=1000000, trials=1000
simulated mean = 100
analytic estimate = 99

The analytic formula is the same as for the number of people with a shared birthday; replace the number of days $d$ with $M$.

The program sets the seed of the random number generator. This allows repeatable results even for randomly generated numbers.

Exercise 1.21

Try changing the relative magnitudes of $N$ and $M$ in the previous exercise to see how the number of duplicates increase as $M$ drops, especially when $M \ll N$. The random permutation model assumes that all elements are distinct and all possible $N!$ permutations are equally likely to occur. Nevertheless, even in the presence of many duplicates, Program 1.2 retains good performance. As emphasized in Sedgewick’s paper Quicksort with Equal Keys., the evidence in favor of stopping the scanning pointers on keys equal to the partitioning element in quicksort is overwhelming. This is exactly how partitioning works in Program 1.2.

There are also other schemes to efficiently handle duplicates. The Algorithms, 4th Edition by RS, KW book’s website, has an extensive treatment of quicksort, including variants like fast 3-way and dual-pivot. There’s also background information about entropy optimal sorting, which states the following

Arrays with large numbers of duplicate sort keys arise frequently in applications. In such applications, there’s potential to reduce the time of the sort from linearithmic to linear.

Thus, this is one example where the random permutation model is inaccurate. Of course, the story can go the other way around when partitioning doesn’t account for duplicates. In this case, quicksort may show quadratic runtime.

Exercise 1.22

Essentially, the distribution of keys is "asymptotically" immaterial for mergesort, as it achieves $\Theta(N\lg N)$ runtime in all cases. The sorting numbers specify the worst-case number of comparisons made by mergesort (see also Exercise 1.5). The best case takes about half as many comparisons as its worst case; this doesn’t apply to Program 1.1 (see the next exercise). All in all, something like Table 1.1 isn’t useful to get insight into stochastic fluctuations.

On the other hand, Table 1.1 could validate a model, implementation and/or analysis. It could pinpoint awkward implementation-related issues, perhaps bugs, if the empirical evidence goes against mathematical predictions, and/or it may assure us that the model for a new variant of mergesort aligns well with empirical data.

Exercise 1.23

The running time of mergesort, as implemented in Program 1.1, depends only on the number of elements in the array being sorted, not on their arrangement. Therefore, the standard deviation in the number of compares is zero, since the input size fully determines the cost.