CODEWITHSUNDEEP
algorithmselection
Artur A
Artur A

Reputation: 297

How to understand the complexity of medians of medians algorithm?

I am following the explanation described here https://brilliant.org/wiki/median-finding-algorithm/ Complexity of the Median-of-medians Algorithm part and it describes about 3n/10 best case and 7n/10 worse case I don't understand how it gets 3n/10 and 7n/10 parts ? while it mentioned that "For each of these elements, there are two elements that are smaller than it (since these elements were medians in lists of five elements—two elements were smaller and two elements were larger)."

Upvotes: 2

Views: 1345

Answers (2)

user1196549
user1196549

Reputation:

The key to the success of this algorithm is that every step discards a constant fraction of the elements.

The median of 2k+1 has k elements on either sides. Then the median of medians of (2k+1)(2l+1) elements has certainly (k+1)(l+1)-1 elements on either sides (every median is no smaller than k+1 elements and there are l+1 medians, all no smaller than the median of medians).

The fraction is ((k+1)(l+1)-1)/(2k+1)(2l+1). In the case of k=2, we have (3(l+1)-1)/5(2l+1) ~ 3l/10.

Upvotes: 0

moreON
moreON

Reputation: 2008

After dividing the list into n/5 groups of 5, and finding the median of medians p, you need to determine a worst case for how many elements you still have to look for the true median in.

Consider how many elements of the list must be smaller than p (or equal to, which in the simpler list of distinct elements case is only p)

Half of the n/5 groups have a median smaller than p. In these groups, there are 3 elements - the median, and the two smaller values - that must be smaller than p. We don't know if the larger elements are larger than p and we don't know if any of the elements in the groups with medians larger than p have elements smaller than p.

So in the worst case, we determine that 1/2 * n/5 groups - n/10 groups - each have 3 elements that are definitely smaller than p. That's 3n/10 elements. In the worst case all other elements are larger than p, this leaves 7n/10 elements larger than p to recursively perform this algorithm on.

Upvotes: 1

Related Questions