- #1
evinda
Gold Member
MHB
- 3,836
- 0
Hello! (Wave)
The [m]SELECT[/m] algorithm determines the $i$th smallest element of an input array of $n>1$
distinct elements by executing the following steps.
Can the algorithm achieve linear execution time if the elements get divided into groups of $7$?
Show that if groups of $3$ are used , linear execution time cannot be achieved.
How can we deduce if the algorithm can achieve linear execution time if the elements get divided into groups of $7$? (Thinking)
The [m]SELECT[/m] algorithm determines the $i$th smallest element of an input array of $n>1$
distinct elements by executing the following steps.
1. Divide the $n$ elements of the input array into $\lfloor \frac{n}{5} \rfloor $ groups of $5$ elements each and at most one group made up of the remaining $n \mod 5$ elements.
2. Find the median of each of the $\lfloor \frac{n}{5} \rfloor $ groups by first insertion-sorting the elements
of each group (of which there are at most $5$) and then picking the median
from the sorted list of group elements.
3. Use SELECT recursively to find the median $x$ of the $\lfloor \frac{n}{5} \rfloor $ medians found in step $2$. (If there are an even number of medians, then by our convention, $x$ is the lower median.)
4. Partition the input array around the median-of-medians $x$ using the modified
version of PARTITION. Let $k$ be one more than the number of elements on the
low side of the partition, so that $x$ is the $k$th smallest element and there are $n-$k
elements on the high side of the partition.
5. If $i=k$, then return $x$. Otherwise, use SELECT recursively to find the $i$th
smallest element on the low side if $i<k$, or the $i-k$ th smallest element on
the high side if $i>k$.
Can the algorithm achieve linear execution time if the elements get divided into groups of $7$?
Show that if groups of $3$ are used , linear execution time cannot be achieved.
How can we deduce if the algorithm can achieve linear execution time if the elements get divided into groups of $7$? (Thinking)
Last edited:
