Question

Question: Consider the following variation of insertion sort: For 1 ≤ i < n, to insert the element A[i] among A[0] ≤ A[1] ≤ … ≤ A[i-1], do a binary search to find the correct position for A[i].

a. How many key comparisons would be done in the worst case?

b. How many times are elements moved in the worst case?

c. What is the asymptotic order of the worst case running time?

Answer 1

a)For the given array, we want to do insertion sort and the A[i] want to be inserted at its correct position, for that binary search is performed. The worse case conplexity of binary search is O(nlogn).

Therefore the number of key comparison in worst case will be nlogn, where n is the number of elements in the array.

b)Number of times elements moved in worst case will be n².

Since we are performing insertion sort, comparing and swapping are two operations.When the array is already sorted, there is no need for swapping and at that time complexity will be O(n).But here, we want to calculate the number of times elements move in worst case, which means the array is unsorted initially.And it requires both conparison and swapping and thats why the worst case time complexity is O(n²).

C)Asymptotic order of worst case running time of insertion sort is O(n²). The reason is same as explained above.