Question

# In class, we have studied the linear time algorithm for selection. In that algorithm, we have...

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.

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 .