Question 5 (20%) Here is the pseudo code for INSERTION-SORT INSERTION-SORT(A) 1

Question

Question 5 (20%) Here is the pseudo code for INSERTION-SORT INSERTION-SORT(A) 1 for j = 2 to A. length 2 keyAU] 3 Insert AU] into the sorted sequence A[1 ..j -1]. 4 5 while i >0 and Ali] > key 7 i=i-1 8 Ali +11key (a) Observe that the while loop of line 5-7 of the INSERTION-SORT uses linear search to scan through the sorted subarray Al1..j -1]. Can we use a binary search instead to improve the overall worst case running time of insertion sort to ?(n In n)? You must justify your answer. (10 points) (b) INSERTION-SORT can be expressed as a recursive procedure as follows. In order to sort A[1 ..n], we recursively sort A[1..n-1 and then insert A[n] in to the sorted array A[1..n-1]. Write a recurrence for the running time of this recursive version of insertion sort. (10 points)

Explanation / Answer

a)

No, using binary search does not improve the worst case time complexity of Intersection Sort. Because

Using Binary Search, we can find the correct location to put new item BUT still we need to shift all elements right to the correct location , to right by 1. Hence : log(n) + O(n) = O(n) time needed to inset a new item.

hence overall time complexity : O(n^2)

b)

T(n) = T(n-1) + n

= T(n-2) + (n-1) + n

--------

= T(1) + 2 + 3 + .... + (n-1) + n

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.