Reference no: EM133258601

Question: Consider the following randomized algorithm for Select(S, k) which outputs kth smallest key from a set S of keys. We use pivoting strategy for this. We first select a random pivot r and partition S around r. This will create parts A and B of S such that all the keys in A are smaller than r and all the keys in B are bigger than r.

Depending on the value k and size of A, we decide to recurse either on A or B. Both A and B are smaller problems than the original. However, to ensure that they are smaller by at least some constant fraction. So we call, r a good pivot if it is ranked within 25% to 75% of set S. What is the probability of finding a good pivot? Next, we see that at every good pivot the problem size reduces by 75% of the original. So how many good pivots will guarantee that the problem size goes down to 1 starting from the original set S of cardinality |S| = n.

To ensure those many good pivots how many pivots totally will be required to be chosen over the entire algorithm. This is asking to find the expected number of coin tosses do you need to get k heads. Let's call this expectation of random variable X (number of coin tosses). Break it up into X1, X2, ..., Xk and find X.