Question

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.

Answer 1

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 .