GATE 2003 Example on Insertion Sort

The unusual \(\Theta(n^2)\) implementation of Insertion Sort to sort an array uses linear search to identify the position where and
element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position,
the worst case running time will be:

A) Remains \(\Theta(n^2)\)

B) become \(\Theta(n(\log n)^2)\)

C) become \(\Theta(n)\)

d) become \(\Theta(n\log n)\)

void insertionSort(int arr[], int n)
   int i, key, j;
   for (i = 1; i < n; i++)
       key = arr[i];
       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;


Consider, Intermediate state of Array (containing numbers) while the execution of insertion sort :

 {Here, numbers to the left of number-0 are sorted }

When linear search is used

Time to find the correct position of key \(\Theta(n)\)

Time to move the elements to make space for key : \(\Theta(n)\)

Total elements = n

\(\therefore Total\ \ Time = n(\Theta(n) + \Theta(n)) = \Theta(n^2)\)


When binary search is used

Time to find the correct position of key : \(\Theta(\log n)\)

Time to move the elements in the array to make space for key \(\Theta(n)\)

Total elements = \(n\)

\(\therefore Total \ \ Time = n(\Theta(\log n) + \Theta(n)) = \Theta(n^2)\)

Hence, Although we made impovement over the searching for the position of the key, but we still need to move the elements which'll take the same time \(\Theta(n)\). Therefore the total time remains same i.e \(\Theta(n^2)\)

Ans (A)

ALOK GUPTA @galok1001 19 Dec 2017 02:55 am