# Cormen Edition 3 Exercise 7.2 Question 5 (Page No. 178)

44 views
Suppose that the splits at every level of quicksort are in the proportion $1-\alpha$ to $\alpha$, where $0<\alpha\leq1/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.)

## Related questions

1
61 views
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 ... problem of sorting almost-sorted input. Argue that the procedure INSERTION-SORT would tend to beat the procedure QUICKSORT on this problem.
Show that the running time of QUICKSORT is $\Theta(n^2)$ when the array $A$ contains distinct elements and is sorted in decreasing order.
What is the running time of QUICKSORT when all elements of the array $A$ have the same value?
We can improve the running time of quicksort in practice by taking advantage of the fast running time of insertion sort when its input is nearly sorted. Upon calling quicksort on a subarray with fewer than $k$ elements, let it simply return without sorting the subarray. After the top-level ... runs in $O(nk+n\ lg\ (n/k))$ expected time. How should we pick $k$, both in theory and in practice?