Question

help with algorithm problems

just answer part A

Compare the text's implementation of insertion sort with the following version 8. ALGORITHM InsertSort2(A[0..n - 1]) for i1 to n1 do ji-1 while j 0 and A[j]> A[j +1] do swap(A[ Aj1]) (2 points) What is the time efficiency of this version of the algorithm? a. b. (4 points) How is the time efficiency of this modified algorithm compared to that of the version given in Section 4.1 of your book?

Answer 1

The for loop runs (n-1) times, for all the three cases

n-1 Σ1)-n-1 1

Best case: (when the array is already sorted)

It doesn't run the while loop even once.

Therefore, Best case time effeciency = $\Omega \left ( n \right )$

Average case

While loop runs on the average of (n-2)/2 times.

Therefore, Time complexity = (n-1)(n-2)/2 =

e (n

Worst case: (when the loop is sorted in the reverse order i.e ascending instead of descending or vice versa)

While loop runs (n-2) times.

Therefore, Time complexity = (n-1)(n-2) = ​​​​​​​

2Y O(n