about Select algorithm

Question

Hi I have read about the selection algorithm and I have a question maybe it looks silly!!! but why we consider the array as groups of 5 elements ?? can we consider it with 7 or 3 elements??thanks also is there any link to help me for understanding this aim better?

also this is my proof when we consider the array with 3 elements and it still is order of n,why?is this correct?

T(n)<=T(n/3)+T(n/3)+theta(n)
claim:  T(n)<=cn
proof:   For all k<=n  : T(n)<=ck
  T(n)<=(nc/3)+(nc/3)+theta(n)
  T(n)<= (2nc/3)+theta(n)
  T(n)<=cn-(cn/3-theta(n))    and  for c>=3 theta(n)  this algorithm with this condition will have an order of n,too  !!!!

Answer 1

A little bit of googling and I found this. There is a very small section on why 5, but it doesn't really answer your question specifically other than to say that it is the smallest possible odd number that can be used (must be odd to give a median). There is some mathematical proof that it can't be 3 (but I don't really understand it myself). I think it is basically saying it can any odd number, 5 or greater, but the smaller the better, I guess because it will be quicker to find the median in the smaller group?

Answer 2

I think you made a mistake for T(n). It should be T(n)=T(n/3)+T(2n/3)+O(n).

The T(n/3) is for finding the pivot (median of medians). Only half of all the n/3 groups have a median smaller than the pivot. Those groups have 2 elements smaller than the pivot. Giving 2*(1/2 * n/3) == n/3 elements smaller than the pivot. Thus only 33% must be smaller than the pivot (and 33% must be greater than the pivot). So, in worse case you still have 66% for the next iteration, T(2n/3).

I can't read your proof well, but now it is impossible to prove it. Right?