USA: +1 (725) 712-1730 
Sign in
Consider the given array InsertionSort algorithm and answer the following:
Algorithm InsertionSort(A):
Input: An array A of n comparable elements
Output: The array A with elements rearranged in increasing order
for i ← 1 to n−1 do
{Insert A[i] at its proper location in A[0], A[1], …, A[i−1]}
cur ← A[i]
j ← i−1
while j ≥ 0 and a[j] > cur do
A[j+1] ← A[j]
j ← j−1
A[j+1] ← cur {cur is now in the right place}
A. Give a big – Oh characterization, in terms of n, of the running time for the InsertionSort algorithm.Explain your answer.
B. Identify the best case and the worst case of the InsertionSort algorithm. Explain your answer.
Expert Answer
A)
For the big-oh characterization we have to consider worst case scenario :
Worst case : Array is sorted in reverse order.
For big-oh characterization :
in first iteration, first 2 elements will be swapped. (1 comparison and swapped. )
in second iteration, first 3 elements will be swapped. (2 comparisons and then swapped. )
in third iteration, first 4 elements will be swapped. (3 comparisons and swapped. )
.
.
in last(n-1)th iteration, all elements will be swapped. (n-1 comparison and swapped.)
hence total work = 1 + 2 + 3 + … + n-1 = (n-1)n / 2 = O(n2)
B)
Best case :
When array is already sorted then there is no need to swap elements at all. Hence Sorted Array is best case for Insertion sort.
Worst case :
When array is sorted in reversed order then it is a worst case for Insertion sort, as all i-1 elements has to be swapped in ith iteration.
if you have any doubts, you can ask in comment section.
