Median of medians

The median of medians is an approximate Selection Algorithm frequently used to supply a good pivot for an exact selection algorithm, most commonly Quickselect.

Linear Quick Select:

1. Median of medians ($n/5$ groups of $5$)
2. Median select recursively

$\Rightarrow$ $T(n)\in O(n)$

gap-in-knowledge Wery confusing topic for me.

Example given in the lecture notes for CS341: Divide input into $n/5$ in groups size of 5 each. Best case median is in 3n/10 and worst case is 7n/10. I don’t understand how i can find the best case and worst case? $T(n)=T(3n/10)+T(7n/10)+O(n)$

Question:

• Median of Medians with different group sizes: In class we say an algorithm for median of medians
• that splits the input into $n/5$ groups of size $5$ each, finds the median of each group, and uses the median of medians as a pivot for the selection algorithm. Suppose the algorithm is modified to split into n/3 groups of size 3 each, what is the recurrence relation for the time complexity of the algorithm? Is the solution linear time? What if we split into n groups of size n each?

I'm still very confused on how to decide the best and worst case.

Ask sophia about it perhaps.