Describe how the number of comparisons used in the worst case changes when the s
ID: 3795317 • Letter: D
Question
Describe how the number of comparisons used in the worst case changes when the size of the list to be sorted doubles from n to 2*n, where n is a positive integer when these sorting algorithms are used a. The selection sort begins by finding the least element in the list. This element is swapped to the front. Then the least element among the remaining elements is found and swapped into the second position. This procedure is repeated until the entire list has been sorted b. The binary insertion sort is a variation of the insertion sort that uses a binary search technique rather than a linear search technique to identify the location to insert the i'th element in the correct place among the previously sorted elements.Explanation / Answer
a)
when size of array is s, worst case of selection sort takes s(s-1)/2 comparisions.
So, Change in comparisions = [ 2n(2n - 1)/2] - [ n(n-1)/2 ]
= (3n^2 - n)/2
b) when size of array is s, binary insertion sort takes (log1 + log2 + log3 + ..... + log(n-1)) comparisions
= log((s-1)!) comparisions
So, Change in comparisions
= [log((2n - 1)!)] - [log(n - 1)!]
= log( (2n - 1)! / (n - 1)!)