CODEWITHSUNDEEP
algorithmrandom
Aditya Nambiar
Aditya Nambiar

Reputation: 886

Expected running time to find Randomized Median

I have tried hard , but i'm unable to come up with the expected running time for the number of comparisons to find the Randomized Median(finding the median of an unsorted array in order n time). Also i wanted to make sure that we CANNOT take expectation of the recurrence that we use to find the randomized median , or any other recurrence in any other problem as they belong to different probability spaces? Is this statement right?

Upvotes: 0

Views: 371

Answers (1)

pentadecagon
pentadecagon

Reputation: 4847

This depends on the algorithm, the general name of the problem is selection algorithm. One popular algorithm is quick select, the average performance of this is linear (i.e. the number of comparisons is k*N, with k typically around 2) but the worst case performance is bad, like O(N*N). There are other algorithms with other trade-offs.

Upvotes: 1

Related Questions