search
Log In
0 votes
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$.

in Algorithms 50 views

1 Answer

0 votes

this might help

 

Related questions

0 votes
1 answer
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$.
asked Jun 28, 2019 in Algorithms akash.dinkar12 95 views
0 votes
2 answers
2
0 votes
1 answer
3
89 views
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.
asked Jun 28, 2019 in Algorithms akash.dinkar12 89 views
0 votes
0 answers
4
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.)
asked Jun 27, 2019 in Algorithms akash.dinkar12 44 views
...