Exercise 7.2-1Use the substitution method to prove that the recurrence $T(n) = T(n-1) + \Theta(n)$ has the solution $T(n) = \Theta(n^2)$, as claimed at the beginning of section 7.2.
solution:
For the upper bound, we guess that $T(n) \leq c_1 n^2$ for some constant $c_1$. Substituting this guess into recurrence, we obtain $T(n) \leq c_1(n-1)^2 + \Theta(n) \leq c_1 n^2 - c_1(2n-1) + \Theta(n) \leq c_1 n^2$, since we can pick the constant $c_1$ large enough so that the $c_1(2n - 1)$ term dominates the $\Theta(n)$ term. Thus, $T(n) = O(n^2)$.
For the lower bound, we guess that $T(n) \geq c_2 n^2$ for some constant $c_2$ in a similar manner as the upper bound. Substituting this guess into recurrence, we obtain $T(n) \geq c_2(n - 1)^2 + \Theta(n) \geq c_2 n^2 - c_2(2n - 1) + \Theta(n) \geq c_2 n^2$, since we can pick the constant $c_2$ small enough so that the $\Theta(n)$ term dominates $c_2(2n - 1)$ term. Thus, $T(n) = \Omega(n^2)$, and we can conclude that $T(n) = \Theta(n^2)$.
Exercise 7.2-2What is the running time of
QUICKSORT when all elements of array
A have the same value?
solution:
Since all elements of array A have the same value, subroutine PARTITION will always split into a subproblem of size $n-1$ and a subproblem of size 0. This is the worst-case. So we expect that running time is $\Theta(n^2)$.
Exercise 7.2-3Show the running time of
QUICKSORT is $\Theta(n^2)$ when the array
A contains distinct elements and is sorted in decreasing order.
solution:
Since array
A is in decreasing order and all elements are distinct, the pivot will be the smallest element in the subroutine
PARTITION. It will always split into a subproblem of size $n-1$ and a subproblem of size 0. This is the worst-case. So we expect that running time is $\Theta(n^2)$.
Exercise 7.2-4Banks often record transactions on an account in order of the times of the transactions, but many people like to receive their bank statements with checks listed in order by check number. People usually write checks in order by check number, and merchants usually cash them with reasonable dispatch. The problem of converting time-of-transaction ordering to check-number ordering is therefore the problem of sorting almost-sorted input. Argue that the procedure
INSERTION-SORT would tend to beat the procedure
QUICKSORT on this problem.
solution:
INSERTION-SORT requires almost $O(n)$ running time to sort an almost-sorted input, however,
QUICKSORT reuqires almost $O(n^2)$ running time. So we use
INSERTION-SORT rather than
QUICKSORT in this situation.
Exercise 7.2-5Suppose that the splits at every level of quicksort are in the proportion $1 - \alpha$ to $\alpha$, where $0 < \alpha \leq 1/2$ is a constant. Show that the minimum depth of a leaf in the recursion tree is approximately $-\lg n / \lg \alpha$ and the maximum depth is approximately $-\lg n / \lg (1-\alpha)$. (Don't worry about integer round-off.)
solution:
Suppose that the minimum depth of a leaf is $d_m$, we can obtain the following equation: $n(\alpha)^{d_m} = 1$. So we can get $d_m = -\log_{\alpha} n = -\lg n / \lg \alpha$. Suppose that the maximum depth of a leaf is $d_M$. We can solve the following equation: $n(1 - \alpha)^{d_M} = 1$to get $d_M$. Thus, $d_M = -\log_{1 - \alpha} n = -\lg n / \lg (1 - \alpha)$.
Exercise 7.2-6Argue that for any constant $0 < \alpha \leq 1/2$, the probability is approximately $1 - 2\alpha$ that on a random input array,
PARTITION produces a split more balanced than $1 - \alpha$ to $\alpha$.
solution:
Suppose that the split is distributed uniformly, and it is more balanced if the split is 1:1. If the split is $1-\alpha$ : $\alpha$ now, then we can get a more balanced split with the probability $2(1/2 - \alpha) = 1 - 2\alpha$.
