Question: In class we considered the Select algorithm, which determines the i th smallest element in an array of size n in O(n) time for the

 In class we considered the Select algorithm, which determines the i

In class we considered the Select algorithm, which determines the i th smallest element in an array of size n in O(n) time for the worst case input. The first step of this algorithm is division into n/5 groups of 5 elements each. Consider other two versions of this algorithm: the first one uses division into n/3 groups of 3 elements each and the second one uses division into n/7 groups of 7 elements each. Otherwise both algorithms implement the same routine as Select. Which algorithm is asymptotically faster, the one with division into groups of 3 , groups of 5 (standard Select), or groups of 7 ? Prove your statement

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!