7.4 Analysis of quicksort
7.4-1
We guess that $T(n) \geq cn^2$ for some constant c. Substituting this guess into recurrence, we obtain:
$$ \begin{eqnarray} T(n) &=& \max_{0 \leq q \leq n - 1}(T(q) + T(n - q - 1)) + \Theta(n) \\ &\geq& \max_{0 \leq q \leq n - 1}(cq^2 + c(n - q - 1)^2) + \Theta(n) \\ &=& c\max_{0 \leq q \leq n - 1}(q^2 + (n - q - 1)^2) + \Theta(n) \\ &=& c\max_{0 \leq q \leq n - 1}(2q^2 - 2(n - 1)q + (n - 1)^2) + \Theta(n) \end{eqnarray} $$
$f(q) = 2q^2 - 2(n - 1)q + (n - 1)^2$ is monotonically decreasing at $[0, \frac{n - 1}{2}]$, and monotonically increasing at $[\frac{n - 1}{2}, n - 1]$. So $\max_{0 \leq q \leq n - 1}(2q^2 - 2(n - 1)q + (n - 1)^2) = f(0) = f(n) = (n - 1)^2$. Thus:
$$ \begin{eqnarray} T(n) &\geq& c(n - 1)^2 + \Theta(n) \\ &=& c(n - 1)^2 + dn \\ &=& cn^2 + (d - 2c)n + c \\ &>& cn^2 \end{eqnarray} $$
where the last step holds as long as $ d \geq 2c$.
So $T(n) = \Omega(n^2)$
7.4-2
The recurrence for the best-case is $T(n) = 2T(\frac{n}{2}) + \Theta(n)$. Let's solve it with the master method. We have $a = 2, b = 2, f(n) = \Theta(n)$, and thus we have that $n^{\log_b{a}} = n^{\log_2{2}} = n = \Theta(n)$. Since $f(n) = \Theta(n)$, we can apply case 2 of the master theorem and conclude that the solution is $T(n) = \Theta(n\lg{n})$. Thus, $T(n) = \Omega(n\lg{n})$.
7.4-3
We've already knew it in the first exercise.
7.4-4
We have:
$$ \begin{eqnarray} E[X] &=& \sum_{i = 1}^{n - 1}\sum_{j = i + 1}^n \frac{2}{j - i + 1} \\ &=& \sum_{i = 1}^{n - 1}\sum_{k = 1}^{n - i} \frac{2}{k + 1} \\ &\geq& \sum_{i = 1}^{n - 1}\sum_{k = 1}^{n - i} \frac{2}{2k} \\ &=& \sum_{i = 1}^{n - 1}\sum_{k = 1}^{n - i} \frac{1}{k} \\ &=& \sum_{i = 1}^{n - 1}\sum_{k = 1}^{i} \frac{1}{k} \\ &=& \sum_{i = 1}^{n - 1}(\ln{i} + O(1)) & \text{(A.7)} \\ &=& \ln{((n - 1)!)} + (n - 1)O(1) \\ &=& \Omega(n\lg{n}) + O(n) & \text{(Exercise 3.2-3)} \\ &=& \Omega(n\lg{n}) \end{eqnarray} $$
7.4-5
Quicksort splits the array into two parts, let's say $T(n) = T(\alpha{n}) + T((1 - \alpha)n) + \Theta(n)$. In exercise 7.2-5, we know when $0 \leq \alpha \leq \frac{1}{2}$, the minimum depth of a leaf is $\log_{\alpha}{\frac{1}{n}}$ and the maximum depth is $\log_{1 - \alpha}{\frac{1}{n}}$, when $\frac{1}{2} < \alpha < 1$, it's opposite. To make it simple, let the recursion tree depth be $\log_{\beta}n$, since the new algorithm terminates when a subarray contains fewer than k elements, so we have $\frac{n}{\beta^{i}} = k$ and $i = \log_{\beta}{\frac{n}{k}}$, so the depth is $O(\lg{\frac{n}{k}})$. Since each recursion tree level costs $O(n)$, the running time of quicksort is $O(n\lg{\frac{n}{k}})$.
The last step is sorting the array by insertion sort. Let's assume n is exactly divisible by k, thus, after quicksort, the $\frac{n}{k}$ subarrays (each with length $\frac{n}{k}$) is sorted, but it's not sorted within the subarray. It requires $O(k^2)$ to sort each subarray, so it requires $\frac{n}{k}k^2 = nk$ to sort entir array.
So the running time is $O(nk + n\lg{\frac{n}{k}})$.
In order to beat quicksort, we need to find a k such that $O(nk + n\lg{\frac{n}{k}}) < O(n\lg{n})$, let's compare $nk + n\lg{\frac{n}{k}}$ and $n\lg{n}$.
$$ \begin{eqnarray} nk + n\lg{\frac{n}{k}} - n\lg{n} &=& nk + n\lg{\frac{1}{k}} \\ &=& nk - n\lg{k} \\ &=& n(k - \lg{k}) \end{eqnarray} $$
But k grows faster than $\lg{k}$, so we cannot pick a good k here. Thus we can multiply a constant c to $n\lg{n}$. Thus:
$$ \begin{eqnarray} nk + n\lg{\frac{n}{k}} - cn\lg{n} &=& nk + n\lg{n} - n\lg{k} - cn\lg{n} \\ &=& n(\lg{2^k} + \lg{n} - \lg{k} - \lg{n^c}) \\ &=& n\lg{\frac{2^k}{kn^{c - 1}}} \end{eqnarray} $$
So we only need to find a k that satifies $\frac{2^k}{kn^{c - 1}} < 1$, which is possible.
In practice, we need to do some tests to find a proper k.