In class we have studied the linear time algorithm for selec

In class, we have studied the linear time algorithm for selection. In that algorithm, we have used groups of size 5. Suppose we are using groups of size 13.

• derive the corresponding recurrence formula.

• What is the corresponding time complexity of the algorithm?

I found the reccurance relation to be T(n)=O(n)+T(n/13)+T(19n/26), but I am having trouble finding the time complexity. Also I really want to learn this, so a detailed response would be nice. I believe it is O(n) but I am not sure as to why.

Solution

For a given set of \'13\' elements the recurrence relation is, T(n)=O(n)+T(n/13)+T(19n/26),

By using the recurrence relation the time complexity can be derived as,

Assume that T (n)< C*n

T (n) = a*n + T (n/13) + T (19n/26)

C*n >= T(n/13) +T(19n/26) + a*n

C*n >= C*n/13+ C*19*n/26 + a*n

C >= 21*C/26 +a

C/26 >= a

C >= 26*a

There exists a constant , so that T (n) = O (n)

If the group is of size less than 5 , then T (n) > O (n) , Hence gouping size of 5 or more than 5 is optimal .