CODEWITHSUNDEEP
complexity-theory
user2081740
user2081740

Reputation: 91

average case running time of randomized median selection

here is an algorithm for finding median of an array of n(odd) distinct numbers. what is the avg. running time of this algorithm

1. Uniformly at random, pick an entry i in A
2. Determine s, the number of entries in A that are smaller than i
3. If s = (n − 1)/2, then return i
4. Else goto 1

i am getting like theta(infinity), which is quit impossible. Can someone help me?

Upvotes: 0

Views: 182

Answers (1)

chodgson
chodgson

Reputation: 36

I don't think you can actually calculate the average run time of this algorithm, as it is possible that it would sometimes never complete - ie. your answer of infinite time is correct.

However, you can use probability to determine the "expected" time. Your question is essentially akin to "How many lottery tickets should I expect to buy before I win?" The probability of randomly picking the correct median is 1/n. So in order to get to P=1 you would expect to pick n times. Given that the time to determine whether the random selection is actually the median requires comparing it against every other entry, the expected overall time would be O(n^2), with best case of o(n) and worst case of o(infinity).

Upvotes: 1

Related Questions