7.2 Performance of quicksort

7.2-1

We start by assuming that this bound holds for all possitive m < n, in particular for m = n - 1, yielding $T(n - 1) \leq c(n - 1)^2$. Substituting into the recurrence yields:

$T(n) = T(n - 1) + \Theta(n) \leq c(n - 1)^2 + dn = cn^2 + (d-2c)n + c \leq cn^2$

where the last step holds as long as $c > \frac{d}{2}$ and $n \geq \frac{c}{2c - d}$.

7.2-2

When all elements of array A have the same value, the PARTITION method returns r, thus it reduces the problem size to n - 1 and 0, which yields the recurrence in the above exercise. So the running time is $\Theta(n^2)$.

7.2-3

When the array A contains decreasing sorted elements, the PARTITION method returns p, thus it reduces the problem size to 0 and n - 1, same like the above exercise. The running time is $\Theta(n^2)$.

7.2-4

Suppose there are k exceptions in an almost-sorted array, in INSERTION-SORT, we need to move the k exceptions to right position, each takes at most $O(n)$, so the total running time is O(n + kn). When k is small enough, INSERTION-SORT tends to be linear sort.

In QUICKSORT, we need to split the array into two parts, since the array is almost-sorted, it's quite possible that it will create 0 size subarray, thus the running time tends to be $O(n^2)$.

So for an almost-sorted array, INSERTION-SORT would tend to beat QUICKSORT.

7.2-5

We have proved it in exercise 4.4-9. When $0 < \alpha \leq \frac{1}{2}$, the minimum depth of a leaf is $\log_{\alpha}{\frac{1}{n}} = -\log_{\alpha}{n} = -\frac{\lg{n}}{\lg{\alpha}}$. The maximum depth is $\log_{1 - \alpha}{\frac{1}{n}} = -\log_{1 - \alpha}{n} = -\frac{\lg{n}}{\lg{1 - \alpha}}$.

7.2-6

The splits at each level quicksort are in the proportion $1 - \alpha$ and $\alpha$, thus the probability that PARTITION produces a more balanced split is $\frac{(1 - \alpha - \alpha)n}{n} = 1 - 2\alpha$.