Consider the linear time selection algorithm select(A, k) (20 pts) Consider all
ID: 3718299 • 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
Select(A,k) to split the array of q elements where q=5,6,7,8
recurence to split array of of size q is:
T(k)= (k/q)T(q)+O(k/q) inertion sort is used to sort the array of size q and O(k/q) is time to split.
for q=5 Array A of size k is divided in k/5 group and array of smallest size will be sorted by using insertion sort.
T(k)= (k/5)T(5)+O(k/5)
= (k/5).10+ O(k/5) (T(5) will take at most 10 comparison to sort the element of array size 5)
= 2*k+O(k+5)
for q=6
T(k)= (k/6)T(6)+O(k/6)
=(k/6)15+O(k/6)
= 2.5*k+O(k/6)
simillarily q=7
T(k)=(k/7)*21+O(k/7)
=3*k+O(k/7)
for q=8
T(k)=(k/8)*28+O(k/8)
=3.5*k+O(k/8)
if group size increses number of element is prosessed is increases but there is decrment of number of group if we consider if it take linear time then q=5 is best to choose median and further to sort subarray of seze greater then 5.