Consider the linear time selection algorithm select(A, k) (20 pts) Consider all
ID: 3716655 • Letter: C
Question
Consider the linear time selection algorithm select(A, k)
(20 pts) Consider all versions of select(A, k) that splits A into arrays of q elements where q=5, 6, 7, 8, …. Which value of q do you think makes the algorithm fastest? Find the number of comparisons as the speed index for each q as accurate as you can. (You can use merge sort, selection sort, or insertion sort etc to sort small arrays of q elements. But you must choose and fix your sorting algorithm before starting the analysis. Then count the total number of comparisons for each q to decide the best value. Show your best upper bound on the number of comparisons. )
Explanation / Answer
Size 5is best one because it takes less number of partion and less size. others increase rduce the number of partion but increase the size of partion.