7.4 Analysis of quicksort

7.4-1

Show that the recurrence

$$ \begin{aligned} T(n) = \max \lbrace T(q) + T(n-q-1): 0\leq q \leq n-1\rbrace + \Theta(n) \end{aligned} $$

has a lower bound of $T(n) = \Omega(n^2)$.

Assume $T(n) \geq cn^2(c \leq 1)$

$$ \begin{aligned} T(n) & = \max \lbrace T(q) + T(n-q-1): 0\leq q \leq n-1\rbrace + \Theta(n)\cr & \geq \max \lbrace cq^2 + c(n-q-1)^2: 0\leq q \leq n-1\rbrace + \Theta(n)\cr & = \max \lbrace cq^2 + cn^2 - 2c(q+1)n+c(q+1)^2: 0\leq q \leq n-1\rbrace + \Theta(n)\cr & = \max \lbrace cn^2 - 2c(q+1)n + c(2q^2 +2q+1): 0\leq q \leq n-1\rbrace + \Theta(n)\cr T(n,q) & = cn^2 - 2c(q+1)n + c(2q^2 +2q+1)\cr \frac{dT(n,q)}{dq} & = 4q+2-2n\cr T(n) & = T(n,0) + \Theta(n)\cr & = cn^2 -2cn + c +\Theta(n)\cr & \geq cn^2\cr \end{aligned} $$

The last step hold for $c\leq d$, while $d$ is the minimum constant facotr hiden in $\Theta(n)$.

7.4-2

Show that quicksort's best-case running time is $\Omega(n\lg n)$.

$$ \begin{aligned} T(n) & = \min \lbrace T(q) + T(n-q-1): 0\leq q \leq n-1\rbrace + \Theta(n)\cr \end{aligned} $$

Assume $T(n)\geq cn\lg n$

$$ \begin{aligned} T(n) & \geq \min \lbrace cq\lg q + c(n-q-1)\lg(n-q-1): 0\leq q \leq n-1\rbrace + \Theta(n)\cr \frac{dT(n,q)}{d(q)} & = c\lg q - c\lg(n-q-1)\cr T(n) & \geq T(n,\frac{n-1}{2})+\Theta(n)\cr & = 2T(\frac{n-1}{2}) + \Theta(n)\cr & \geq 2c(\frac{n-1}{2})\lg(\frac{n-1}{2}) + \Theta(n)\cr & = c(n-1)\lg(n-1) -c(n-1)\lg 2 + \Theta(n)\cr & = cn\lg n -c\lg(n-1) - cn\lg(\frac{2n}{n-1})+2c\lg 2 + \Theta(n)\cr & \geq cn\lg n\cr \end{aligned} $$

The last step hold for $-cn\lg(\frac{2n}{n-1})+\Theta(n)\geq c\lg(n-1)$

7.4-3

Show that the expression $q^{2} + (n-q-1)^{2}$ achieves its maximum value over $q=0,1,...,n-1$ when $q=0$ or $q=n-1$.

$$ \begin{aligned} f(q) & = q^{2} + (n-q-1)^{2}:q=0,1,...,n-1\cr \frac{df(q)}{dq} & = 2q - 2(n-q-1)\cr & = 4q - 2n + 2 \cr \frac{df(q)}{dq} & < 0 \text{ for } q < \frac{n-1}{2}\cr \frac{df(q)}{dq} & > 0 \text{ for } q > \frac{n-1}{2}\cr \max(f(q)) & = f(0) \text{ or } f( n - 1 )\cr \end{aligned} $$

7.4-4

Show that RANDOMIZED-QUICKSORT's expected running time is $\Omega(n\lg n)$.

Let $R[1:n]$ be the sorted array. The probability that $R[i]$ is compared with $Rj$ in original array is $\frac{2}{j-i}$.

$X_{ij} = I \lbrace R[i] \text{ is compared with }R[j]\rbrace$

The expected running time of RANDOMIZED-QUICKSORT is:

$$ \begin{aligned}

E[X] & = \sum_{0 < i < j \leq n} E[X_{ij}]\cr
& = \sum_{0 < i <n}\sum_{j=i+1}^{n}\frac{2}{j-i+1}\cr
& = \sum_{0 < i <n}\sum_{j=1}^{n-i}\frac{2}{j+1}\cr
& > \sum_{0 < i < n/2}\sum_{j=1}^{n/2}\frac{2}{j+1}\cr
& = \sum_{0 \leq i < n/2}\Omega(\lg n)\cr
& = \Omega(n\lg n)\cr

\end{aligned} $$

7.4-5

Coarsening the recursion, as we did in Problem 2-1 for merge sort, is a common way to improve the running time of quicksort in practice. We modify the base case of the recursion so that if the array has fewer than $k$ elements, the subarray is sorted by insertion sort, rather than by continued recursive calls to quicksort. Argue that the randomized version of this sorting algorithm runs in $O(nk+n\lg(n/k))$ expected time. How should you pick $k$, both in theory and in practice?

In quicksort part, since the procedure stop in level $\lg(n/k)$, its expected running time is $O(n\lg(n/k))$.

In insertion sort part, its expected running time is $\frac{n}{k}O(k^2) = O(nk)$

So the overall running is $O(nk+n\lg(n/k))$

In theory, we need to solve $O(nk+n\lg(n/k)) < O(n\lg(n))$, no solution.

In practice, we need to solve

$$ \begin{aligned} c_1nk + c_2n\lg(n/k) < c_2n\lg(n)\cr \implies c_1k + c_2\lg(n)-c_2\lg k < c_2 \lg n\cr \implies c_1k -c_2\lg k <0\cr \end{aligned} $$

$\star$ 7.4-6

Consider modifying the PARTITION procedure by randomly picking three elements from subarray $A[p:r]$ and partitioning about their median (the middle value of the three elements). Approximate the probability of getting worse than an $\alpha$-to-$(1-\alpha)$ split, as a function of $\alpha$ in the range $0 < \alpha < 1/2$.

$$ \begin{aligned} P & =P(\text{three in middle } (1 - 2\alpha)n) + P(\text{one in smallest }\alpha n,\text{one in middle,one in largest})\cr & = (1-2\alpha)^{3} + P(3,3)\alpha^{2}(1-2\alpha)\cr & = -8\alpha^3 +12\alpha^2 - 6 \alpha +1 +6\alpha^2-12\alpha^3\cr & = 1 -6\alpha + 12\alpha^2 -20\alpha^3\cr \end{aligned} $$