Suppose you''re given n numbers and asked to find a number that is greater than or equal to the median
a) What is the lower bound for the worst case complexity of this problem?
b) Describe a random algorithm that returns a valid result with probability p=1/2 ? ( Do not write a C/C++ Code, just describe)
c) For this problem, 1/2 is clearly not an acceptable probability. Describe a way to amplify this probability by calling the random algorithm you proposed at part b as a subroutine several times. Analytically how does it increase the probability p?