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$.