We have studied the linear time selection algorithm applied on n elements.

Assume that all n elements are different.

In the algorithm we have studied, we used group size of $5.$

We proved that the number of elements that are guaranteed to be

larger than the median of medians is lower bounded by

G$($n$,5)=3$n$/10-6.$

Similarly, the number of elements that are guaranteed to be

smaller than the median of medians is also lower bounded by G$($n$,5).$

Therefore, the number of elements on either side of the median of medians

after the partition is upper bounded by U$($n$,5)=$ n $-$ G$($n$,5)=7$n$/10+6.$

We concluded that the time complexity T$($n$)$ of the algorithm satisfy the relation

T$($n$)<=$ T$($n$/5)+$ T$(7$n$/10+6)+$ Theta$($n$).$

This leads to T$($n$)=$ Theta$($n$).$

Suppose that we use group size $7($instead of $5),$ what is G$($n$,7)?$

Suppose that we use group size $7($instead of $5),$ what is U$($n$,7)?$

Suppose that we use group size $7($instead of $5),$ what is the recurrence relation for T$($n$)?$

Suppose that we use group size $7($instead of $5),$ what is the corresponding worst$-$case running time of the algorithm?

Suppose that we use group size $9($instead of $5),$ what is G$($n$,9)?$

Suppose that we use group size $9($instead of $5),$ what is U$($n$,9)?$

Suppose that we use group size $9($instead of $5),$ what is the recurrence relation for T$($n$)?$

Suppose that we use group size $9($instead of $5),$ what is the corresponding worst$-$case running time of the algorithm?

Analysis of the Algorithm:

For simplicity, assume all n elements in A are distinct.

At least half of the medians found in Step$2$ are $>$ x

At least half of the n$/5$ groups $($except $2$ groups, i$.$e$.,$ the group that has fewer than $5$ elements and the group that contains x itself$)$ contribute at least $3$ elements that are $>$ x$.$

Therefore, the number of elements that are greater than x is at least $3*(($n$/5)/2-2)>=(((3*$n$)/10-6))$

Similarly, the number of elements that are $<$ x is at least $3$n$/106.$

SELECT is called recursively on at most $7$n$/10+6($i$.$e$.,$ n $(3$n$/10-6))$ elements in Step$5.$

Worst$-$Case Running Time of SELECT$($A$,$ p$,$ r$,$ i$)$:

$$ Steps $1,2,$ and $4$: O$($n$)$ time.

$($Step$2$ consists of O$($n$)$ calls of insertion sort on sets with $<5$ elements each$).$

$$ T$($n$)=$ worst$-$case running time of SELECT on an array with n elements.

$$ Step$3$: T$($n$/5)$ time

$$ Step $5$: T$(7$n$/10+6)$ time $($follows from previous considerations$)$

$$ Thus T$($n$)<=$T$($n$/5)+$T$(7*$n$/10+6)+$b$*$n

We can ignore the ceiling function and the constant $6$ in our analysis.

T$($n$)<=$b$*$n$(1+(9/10)+(9/10)^2+(9/10)^3+...=$ O$($n$)$

SELECT $($A$,$ p$,$ r$,$ i$)$ for finding the $($i$-$p$+1)$th smallest element in A$[$p$..$r$],$ which is the $($i$-$p$+1)$th smallest element of an input array A$[1..$N$].$ Denote n$=$p$-$r$+1.$

Step $1$: Divide the n elements of A$[$p$..$r$]$ into n$/5$ groups of $5$ elements each and at most one group made up of the remaining $($n mod $5)$ elements.

Step $2$: Find the median of each of the n$/5$ groups by insertion sorting the $($at most $5)$ elements of each group and taking its middle element $($if the group has an even # of elements, take the lower of the two medians$).$

Step $3$: Use SELECT recursively to find the median x of the n$/5$ medians found in Step$2$;

Step $4$: Partition A$[$p$..$r$]$ around the median$-$of$-$the$-$medians x using a modified version of quicksort$$s PARTITION that takes x as a parameter and uses x as the pivot element. Let q be the index of the median x$,$ and k$=$q$-($p$-1).$

Step $5$: If i$==$k$,$ return x$.$ Otherwise, use SELECT$($A$,$ p$,$ q$-1,$ i$)$ to find the ih smallest element on the low side, if ik$.$