7.2 Performance of quicksort

7.2-1

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

$$ \begin{aligned} T(n) & = T(n-1) + \Theta(n)\cr & \leq c(n-1)^2 + \Theta(n)\cr & = cn^2 -2cn+c+\Theta(n)\cr & = cn^2-cn +\Theta(n) + c(1-n)\cr & \leq cn^2\cr \end{aligned} $$

The last step holds while $c$ is large enough.

7.2-2

What is the running time of QUICKSORT when all elements of array A have the same value?

Since the size of one side is $n-1$, the other is $0$,the running time is:

$T(n) = T(n-1)+\Theta(n) \implies T(n) = \Theta(n^2)$

7.2-3

Show that the running time of QUICKSORT is $\Theta(n^2)$ when the array $A$ contains distinct elements and is sorted in decreasing order.

Since the array $A$ contains distinct elements and is sorted in decreasing order, the for loop will do nothing, it will divide the array into a subarray with size $n-1$ and the other with size 0, while the decreasing order property maintains.So the running time:

$T(n) = T(n-1)+\Theta(n) \implies T(n) = \Theta(n^2)$

7.2-4

Banks 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. Explain persuasively why the procedure INSERTION-SORT might tend to beat the procedure QUICKSORT on this problem.

For almost-sorted input, the running time of QUICKSORT is $\Theta(n^2)$

The running time of INSERTION-SORT is $\Theta(n+d)$, while $d$ denote the numbers of inversions in input array. For almost-sorted input, $d$ is small, so INSERTION-SORT might tend to beat the procedure QUICKSORT on this problem.

7.2-5

Suppose that the splits at every level of quicksort are in the constant proportion $\alpha$ to $\beta$, where $\alpha + \beta = 1$ and $0 < \alpha \leq \beta < 1$. Show that the minimum depth of a leaf in the recursion tree is approximately $\log_{1/\alpha}n$ and that the maximum depth is approximately $\log_{1/\beta}n$. (Don’t worry about integer round-off.)

For the minimum depth of a leaf, it must corresponds to repeatedly taking the smaller subproblem. Let $k$ be its depth, then we have

$$ \begin{aligned} n\alpha^{k}=1\cr \implies k \log_{1/\alpha}n\cr \end{aligned} $$

For the minimum depth of a leaf, the same:

$$ \begin{aligned} n\beta^{k}=1\cr \implies k \log_{1/\beta}n\cr \end{aligned} $$

7.2-6

Consider an array with distinct elements and for which all permutations of the elements are equally likely. Argue that for any constant $0 < \alpha \leq 1/2$, the probability is approximately $1 - 2\alpha$ that PARTITION produces a split at least as balanced as $1-\alpha$ to $\alpha$.

because all permutations of the elements are equally likely, each element in the array is equally likely to be selected as pivot. To produce a split at least as balanced as $1-\alpha$ to $\alpha$, PARTITION must select the element in $\lbrace x|x_{\alpha n}\leq x \leq x_{(1-\alpha) n}\rbrace$, in which $x_{i}<x_{j}\iff i<j$. The probability is:

$$ \begin{aligned} P = \frac{1-2\alpha}{1}=1-2\alpha; \end{aligned} $$