MHB Can we achieve linear time with groups of 7 in the SELECT algorithm?

[evinda]

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.

• 
  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$.

At the algorithm [m]SELECT[/m], the input elements are divided into groups of $5$.

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)

 

[evinda]

We could find a recurrence relation that describes the algorithm, right? (Thinking)

Could you help me to find the time complexity of each of the steps?

 

[alyafey22]

Do you understand the proof when the length is divided by 5 ?

 

[evinda]

I saw that for the second step, the cost should be $c \cdot \lceil \frac{n}{5} \rceil$. How can this be the cost, although we apply Insertion sort? Also how can we find the cost for the step $5$?

 

[alyafey22]

I saw that for the second step, the cost should be $c \cdot \lceil \frac{n}{5} \rceil$. How can this be the cost, although we apply Insertion sort? Also how can we find the cost for the step $5$?

The insertion sort is done on lists with fixed length equal to 5 , right ?