An Insertion Sort time complexity question

Question : How much time Insertion sort takes to sort an array of size n in below form?

arr[] = 2, 1, 4, 3, 6, 5,….i, i-1, …..n, n-1

Answer : At first look, it seems like Insertion Sort would take O(n2) time, but it actually takes O(n) time

How? Let us take a closer look at below code.

/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
   for (int i = 1; i < n; i++)
       int key = arr[i];
       int j = i-1;
       /* Move elements of arr[0..i-1], that are
          greater than key, to one position ahead
          of their current position */
       while (j >= 0 && arr[j] > key)
           arr[j+1] = arr[j];
           j = j-1;
       arr[j+1] = key;

If we analyze the input carefully we see that every element is only one position away from its position in sorted array. The outer for loop will run till ‘n’ and the inner while loop would take “constant” steps of 1 swap and 2 comparisons. Since, while loop takes constant time and for loop runs for ‘n’ element, so overall complexity is O(n)

Alternate Answer : Another way to look at this is, time taken by Insertion Sort is proportional to number of inversions in an array. In above example type, number of inversions is n/2, so overall time complexity is O(n)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment



load comments

Subscribe to Our Newsletter