Find an exact formula for the number of lines needed to be run in both the inser

Question

Find an exact formula for the number of lines needed to be run in both the insertion sort and merge sort pseudo-code. This formula should be for arrays of size n that are in the reverse of sorted (e.g. [8, 7, 6, 5, 4, 3, 2, 1] with n = 8). Give the ranges of n where merge sort performs better than insertion sort. For full points, you cannot use a recursively defined function for merge sort.

TopDownMerge (A], iBegin, iMiddle, iEnd, B[) i = iBegin, Merge sort IWILL Le tiere are e lements in the teft or right runs... for (k= iBegin; k 1End ; k++) { 1If left run head exists and isexisting right run head. } else t B[k] = A[j]; Insertion sort while i = and A[j] > x end while i-i+1 end while

Explanation / Answer

The Above pseudo-code for Top Down Merge will take O(n) time, as for loop will run N times and statement is for loop take constant time of O(1).

Above pseudo-code for InsertionSort will take O(n2), as outer while loop with run n times, and inner while loop will run :

For i = 1, 1 times, for i = 2, 2 times, for i=3, 3 times. and so on.

1 + 2 + ... + (n-1) + n = n(n+1) / 2, => (n+1) / 2 on average.

Thus the total running time would be O(n*(n+1)/2)* O(1) = O(n*n) = O(n2)

Ranges of n where merge sort performs better than insertion sort :

As above pseudo-code is only for TopDownMerge (merging two arrays), not complete Merge Sort.

MergeSort complete time complexity is O(nlogn) everytime,and Insertion sort is O(n2).

Insertion sort best time O(n), only when Array is already sorted in in increasing order, then second while loop condition A[j] > x result false, thus not executing second loop.

Thus, if array is not sorted/is sorted in decreasing order, then MergeSort will take O(nlogn) and Insertion sort is O(n2).

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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