> For the complete documentation index, see [llms.txt](https://evarga.gitbook.io/sh-aofa/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://evarga.gitbook.io/sh-aofa/introduction/chapter-1-analysis-of-algorithms.md). # 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)$$. {% hint style="info" %} It would be a mistake to set the lower bound to 1, since the book's definition of big-O allows negative functions, too. {% endhint %} ## 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](https://algs4.cs.princeton.edu/22mergesort/), 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](https://algs4.cs.princeton.edu/22mergesort/Merge.java.html); 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](https://www.geeksforgeeks.org/dsa/3-way-merge-sort/) in great detail. Below is the driver code to measure execution time. Replace the original driver code in programs from GeeksforGeeks implementing [standard](https://www.geeksforgeeks.org/dsa/merge-sort/) and 3-way mergesort algorithms. {% code expandable="true" %} ```python 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") ``` {% endcode %} 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 ``` {% hint style="info" %} 3-way mergesort has a lower recursion depth, which may potentially improve performance. The [k-way merge](https://en.wikipedia.org/wiki/K-way_merge_algorithm) is a generalization of this idea. {% endhint %} ## 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](https://en.wikipedia.org/wiki/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 \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](#exercise-1.3). It uses sentinels, like Program 1.1 from the book, so counting the number of comparisons inside the loop is straightforward. {% code expandable="true" %} ```java 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++]; } } } ``` {% endcode %} 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 🌟 {% hint style="success" %} [Algorithm science](https://sedgewick.io/ideas/#algorithm-science) is a methodology for developing machine-independent falsifiable hypotheses. This exercise is about the *doubling hypothesis*. {% endhint %} According to [Exercise 1.1](#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](https://www.geeksforgeeks.org/dsa/merge-sort/) 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](https://algs4.cs.princeton.edu/23quicksort/Sort2distinct.java.html). {% hint style="danger" %} 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). {% endhint %} ## 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. {% hint style="info" %} As an additional practice, solve the LeetCode problem [Sort Colors](https://leetcode.com/problems/sort-colors/). {% endhint %} ## Exercise 1.11 The following Python program implements this concept. The `merge` procedure uses sentinels to be aligned with the version from the book. {% code expandable="true" %} ```python 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}") ``` {% endcode %} 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](https://aofa.cs.princeton.edu/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 🌟 {% hint style="success" %} 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. {% endhint %} The proof below is adopted from [Sedgewick’s PhD thesis](https://sedgewick.io/wp-content/themes/sedgewick/papers/1975Quicksort.pdf). 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](https://en.wikipedia.org/wiki/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 🌟 {% hint style="success" %} This exercise showcases a technique to eliminate dependence on historical data on the RHS of the recurrence relation. {% endhint %} $$ \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 🌟 {% hint style="success" %} 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). {% endhint %} The proof is adopted from [Sedgewick’s PhD thesis](https://sedgewick.io/wp-content/themes/sedgewick/papers/1975Quicksort.pdf). 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\*} $$ {% hint style="warning" %} 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$$. {% endhint %} ## Exercise 1.16 🌟 {% hint style="success" %} 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. {% endhint %} 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 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](#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$)}. $$ {% hint style="info" %} A simple variation of this problem is the [review question Q1.3](https://aofa.cs.princeton.edu/10analysis); the answer is $$B\_{Nk}=\cfrac{k(N+1)}{k+2}\qquad \text{(for $N>k$)}.$$ {% endhint %} ## Exercise 1.17 🌟 {% hint style="success" %} This exercise illustrates the methodology of employing analysis of algorithms in tuning parameters to attain better performance. {% endhint %} 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$)}. $$ {% hint style="warning" %} 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$)}.$$ {% endhint %} ## Exercise 1.18 🌟 {% hint style="success" %} This exercise shows a minimization problem in finding the cutoff value for switching to insertion sort. {% endhint %} 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](https://www.wolframalpha.com/), 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$$. {% hint style="info" %} 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). {% endhint %} ## 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. ```python 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](https://en.wikipedia.org/wiki/Birthday_problem#Number_of_people_with_a_shared_birthday); replace the number of days $$d$$ with $$M$$. {% hint style="info" %} The program sets the seed of the random number generator. This allows repeatable results even for randomly generated numbers. {% endhint %} ## 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](https://sedgewick.io/wp-content/themes/sedgewick/papers/1977Equal.pdf)., 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](https://algs4.cs.princeton.edu/23quicksort/), 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](https://en.wikipedia.org/wiki/Sorting_number) specify the worst-case number of comparisons made by mergesort (see also [Exercise 1.5](#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. --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter: ``` GET https://evarga.gitbook.io/sh-aofa/introduction/chapter-1-analysis-of-algorithms.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.