[Algo] Exercise 7.4

Exercise 7.4-1
Show that in the recurrence $T(n) = \max_{0 \leq q \leq n-1}(T(q) + T(n - q - 1)) + \Theta(n)$, $T(n) = \Omega(n^2)$.
solution:
Assume that $T(n) \geq cn^2$, where c is a constatnt. Substitute into the recurrence, we can obtain that
$$T(n) \geq \max_{0 \leq q \leq n-1} (cq^2 + c(n - q - 1)^2) + \Theta(n),$$
$$T(n) \geq c \max_{0 \leq q \leq n-1} (q^2 + (n - q - 1)^2) + \Theta(n).$$
We know that $(q^2 + (n - q - 1)^2)$ achieves maximum value when $q = 0$ or $q = n - 1$ with maximum value $(n - 1)^2$. Thus, $T(n) \geq c(n-1)^2 + \Theta(n) = cn^2 - c(2n - 1) + \Theta(n)$. Since we can always get a constant c which is dominated by the $\Theta(n)$ term so $T(n) \geq cn^2$.

Exercise 7.4-2
Show that quicksort's best-case running time is $\Omega(n \lg n)$.
solution:
Let quicksort's best-case running time be $T(n)$, and assume that $T(n) \geq cn \lg n$, where c is a constant. And we know that $T(n) = \min_{0 \leq q \leq n-1} (T(q) + T(n - q - 1)) + \Theta(n)$. Substitute $T(n) \geq cn \lg n$ into the above equation we can get the following inequality:
$$T(n) \geq c \times \min_{0 \leq q \leq n-1} (q \lg q + (n - q - 1)\lg(n - q - 1)) + \Theta(n).$$
We now have to get the minimum value of $q \lg q + (n - q - 1)\lg(n - q - 1)$.


what we have to do is compute the derivative and set it to zero to solve it. First, we show how to compute the derivative,
$$y = f(x)^{g(x)} \Rightarrow \frac{dy}{dx} = f(x)^{g(x)}(g^\prime(x)\ln f(x) + g(x) \cdot \frac{f^\prime(x)}{f(x)})$$
Thus, the derivative of $q^{q}(n - q - 1)^{(n - q- 1)}$ is
$$q^{q}(n - q - 1)^{(n - q- 1)}\ln(\frac{q}{n - q - 1}),$$ solve the equation we can get $q = n - q - 1, q = (n - 1)/2$. Furthermore, the second derivative is
$$q^q(n-q-1)^{(n-q-1)}(\ln^2(\frac{q}{n - q - 1}) + \frac{n - 1}{q(n - q - 1)})\geq 0,$$
we can conclude that $q = (n - 1)/2$ achieves a minimum.
When $q = (n - 1)/2$,
$$T(n) \geq c(2 \times \frac{n-1}{2} \lg \frac{n-1}{2}) + \Theta(n) = c[(n - 1) \lg (n - 1) - (n - 1)] + \Theta(n),$$
where
$$\lg(n - 1) = \lg n(1 - \frac{1}{n}) = \lg n + \lg(1 - \frac{1}{n}).$$
We can rewrite it to
$T(n) \geq c[(n - 1)(\lg n + \lg(1 - \frac{1}{n})) - (n - 1)] + \Theta(n)$
$= c[n \lg n + n \lg(1 - \frac{1}{n}) - \lg n - \lg(1 - \frac{1}{n}) - n + 1] + \Theta(n)$
$= cn \lg n + c(n \lg(1 - \frac{1}{n}) - \lg n - \lg(1 - \frac{1}{n}) - n + 1) + \Theta(n),$ and note that
$$n \lg(1 - \frac{1}{n}) = \lg(1 - \frac{1}{n})^n < \lg e^{-1}.$$ Since we can always find an appropriate constant c which is dominated by $\Theta(n)$. Thus, $T(n) \geq cn \lg n$.

Exercise 7.4-3
Show that $q^2 + (n - q - 1)^2$ achieves a maximum over $q = 0, 1, \ldots, n - 1$ when $q = 0$ or $q = n - 1$.
solution:
$q^2 + (n - q - 1)^2 = 2q^2 -2(n - 1)q + (n - 1)^2$, so it is a convex parabola. Local maximum appears at end points.

Exercise 7.4-4
Show that RANDOMIZED-QUICKSORT's expected running time is $\Omega(n \lg n)$.
solution:
Follow equation 7.4, we can rewrite it to:


Exercise 7.4-5
The running time of quicksort can be improved in practice by taking advantage of the fast running time of insertion sort when its input is "nearly" sorted. When quicksort is called on a subarray with fewer than k elements, let it simply return without sorting the subarray. After the top-level call to quicksort returns, run insertion sort on the entire array to finish the sorting process. Argue that this sorting algorithm runs in $O(nk + n\lg(n/k))$ expected time. How should k be picked, both in theory and in practice?
solution:
Since quicksort returns when the subarray is fewer than k elements, its depth is $O(\lg(n/k))$. Running insertion sort on an almost-sorted array is O(nk). Thus the total running time is $O(nk + n\lg(n/k))$.

Exercise 7.4-6
Consider modifying the PARTITION procedure by randomly picking three elements from array A and partitioning about their median (the middle value of the three elements). Approximate the probability of getting at worst an $\alpha$-to-$(1 - \alpha)$ split, as a function of $\alpha$ in the range $0 < \alpha < 1$.
solution:
The answer is straightforward. In order to have an $\alpha$-to-$(1 - \alpha)$ split, we pick up one element from $n\alpha$ elements and one elements from $n(1-\alpha)$ elements. Hence, the probability is $$\frac{(n\alpha)[n(1 - \alpha)]}{C_3^n}$$