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

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.

Explanation / Answer

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 .

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.