Problem:
Observe that the while loop of lines 5 - 7 of the INSERTION-SORT procedure in Section 2.1
uses a linear search to scan (backward) through the sorted subarray A[1 j - 1]. Can we use a
binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of
insertion sort to Θ(n lg n)?
Solution:
No, for finding correct place lets say O(log n) then for moving all the elements will take O(n) time. So, its running time will be O(n^2)
Complexity:
Code:
Observe that the while loop of lines 5 - 7 of the INSERTION-SORT procedure in Section 2.1
uses a linear search to scan (backward) through the sorted subarray A[1 j - 1]. Can we use a
binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of
insertion sort to Θ(n lg n)?
Solution:
No, for finding correct place lets say O(log n) then for moving all the elements will take O(n) time. So, its running time will be O(n^2)
Complexity:
Code:
No comments:
Post a Comment