Pivot games

Computer Science Level pending

What is the probability that in randomized quick-sort, a random pivot selection on an input of \(n\) keys leads to recursive calls, both of which are no smaller than \(\dfrac{n}{ 16}\)?

If the probability can be expressed as \(\dfrac{a}{b}\), where \(a\) and \(b\) are coprime positive integers. Input \(a+b\) as your answer.

Assume the keys are uniform throughout.

×

Problem Loading...

Note Loading...

Set Loading...