Cormen Edition 3 Exercise 7.2 Question 6 (Page No. 179)

50 views

Argue 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$.

this might help

Related questions

1
95 views
Consider modifying the PARTITION procedure by randomly picking three elements from the array $A$ and partitioning about their median (the middle value of the three elements). Approximate the probability of getting at worst a $\alpha$-to-$(1-\alpha)$ split, as a function of $\alpha$ in the range $0<\alpha<1$.
Show that quicksort’s best-case running time is $\Omega(n\ lg\ n)$.
RANDOMIZED-QUICKSORT(A, p, r) 1 if p < r 2 q = RANDOMIZED-PARTITION(A, p, r) 3 RANDOMIZED-QUICKSORT(A, p, q - 1) 4 RANDOMIZED-QUICKSORT(A, q + 1, r) RANDOMIZED-PARTITION(A, p, r) 1 i = RANDOM(p, r) 2 exchange A[r] with A[i] 3 return ... how many calls are made to the random number generator RANDOM in the worst case? How about in the best case? Give your answer in terms of $\Theta$ notation.
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.)