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?
I can pay 6$.
Dear sir,
I am strong in algorithm implementation and analysis. I have deep insight into algorithm complexity analysis in time and space and I am familiar with random algorithm and selection algorithm. I have done similar projects and I can do it with high quality.
Wait for your response
Thank you
BR