Let t_j denote the number of times the while loop test in line 4 is executed for
ID: 3667823 • Letter: L
Question
Let t_j denote the number of times the while loop test in line 4 is executed for that value of j. Fill in for each line of instruction, the number of times the instruction is executed. Derive the expression for the running time of INSERTION_S0RT in terms of n, C_i, and t_j. What is t_j for the best-case scenario, i.e., when the running time of the algorithm is the smallest. Use that to derive the expression for the best-case running time of INSERTION_SORT in terms of n and C_i. What is the best-case time complexity of INSERTION_SORT using the big-O notation? What is t_j for the worst-case scenario, i.e., when the running time of the algorithm is the largest. Use that to derive the expression for the worst-case running time of INSERTION_SORT in terms of n and C_i. What is the worst-case time complexity of INSERTION_SORT using the big-O notation?Explanation / Answer
Insertion Sort Analysis
Based on Insertion Sort Algorithm, we can close look at the insertion sort code, we can notice that every iteration of while loop reduces one inversion.
The while loop executes only if i > j and arr[i] < arr[j].
Therefore total number of while loop iterations (For all values of i) is same as number of inversions. Therefore overall time complexity of the insertion sort is O(n + f(n)) where f(n) is inversion count.
If the inversion count is O(n), then the time complexity of insertion sort is O(n).
In worst case, there can be n*(n-1)/2 inversions.
The worst case occurs when the array is sorted in reverse order. So the worst case time complexity of insertion sort is O(n Square 2).
So Time Complexity of Insertion Sort
In the average case and worst case, it is both O(n^2) and (n^2).
In this case Why we , So analysis of Insertion sort
In the average and worst case insertion sort is (n^2).
Since it is (n^2) in these case, it implies that it is (n^2) and O(n^2) in these cases.
In the best case (a case we rarely care about) insertion sort is (n).
From Big O –notation
We can write like this
Being (n) in the best case implies that it is (n) and O(n) in the best case.
Being O(n) in the best case implies that it is also O(n^2) in the best case.
Simply we can say
Worst case: (n^2)
Best case : (n).
Average case for a random array : (n2).
"Almost sorted" case: (n).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.