Working out the average case performance of the QuickSelect algorithm is quite c

Question

Working out the average case performance of the QuickSelect algorithm is quite complicated, but we

can estimate it.

Assume that:

%u2022 Each call to partition in the QuickSelect algorithm (with the Hoare partition) divides the array

into two equal sized halves (this is what happens on average).

%u2022 K is such that we don't find the k-th smallest element until the last partition (e.g. if we have an

array of size 16 and we want to find the 2nd biggest element).

Under these assumptions how many steps does the QuickSelect algorithm take to compute the k-th

smallest element (i.e. what is the time complexity of QuickSelect).

Justify your answer (you don't need to prove it %u2013 you can if you want %u2013 but you should be able to

convince me why your answer is correct).

Remark: your intuition may be that the time complexity should be log(n), like binary search, but such

an estimate ignores the cost of partitioning

Explanation / Answer

Average complexity of Quick select is O(n)

At every step we partition the array into 2 parts and kth element belong to either one of these partition. Hence on the next step only n/2 elements need to process. in the time taken will be

= n + n/2 +n/4+n/8 ..... A GP and sum will be approx 2n whic is O(n)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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