The unusual $\Theta(n^2)$ implementation of Insertion Sort to sort an array uses linear search to identify the position where an 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

- remain $\Theta(n^2)$
- become $\Theta(n (\log n)^2)$
- become $\Theta(n \log n)$
- become $\Theta(n)$

### 5 Comments

For $n$ element : $n\times 2n=2n^2=O(n^2)$

$2)$ Binary search: $\left | \underbrace{sorted} \right |$ $\leftarrow\left | i \right |: comparisons=logn,swaps=n$

For $n$ element : $n\times (n+logn)=n^2+nlogn=O(n^2)$

## 2 Answers

In insertion sort, with linear search, it takes

(worst case) $n$ comparisons for searching the right position, and $n$ swaps to make room to place the element.

Hence for n elements, a total of $n\times(n+n)$; $n$ for search and $n$ for swaps.

$= \Theta (2n^2) = \Theta (n^2)$

If we replace it with binary search, it takes

(worst case) $\log n$ comparisons for searching the right position, and $n$ swaps to make room to place the element.

Hence for n elements, a total of $n\times(\log n+n)$; $n$ for search and $n$ for swaps.

$= \Theta (n \times \log n + n^2) = \Theta (n^2)$

Hence, **answer is A.**

### 23 Comments

@ryan sequeira You mean for every element in the array we need to do max. n comparisons to search for the right position?

But if you see the code for each iteration, max no. of comparisons that can occur in an iteration will be from j to 1 where j=(i-1) so i.e. i-1-1+1=i-1 where i∈[2,n].

InsertionSort(arr,n) { for i=2 to n { key = arr[i] j = i-1 while (j > 0 && arr[j] > key) // will run from j=(i-1) to max. j=1 { arr[j+1] = arr[j] j = j-1 } arr[j+1] = key } }

So what I mean to say is no. of comparisons is not n for all elements and neither is the no. of swaps. It depends on the element's position in the array. Isn't it so? Correct me if it is wrong.

The answer is still the same though.

@Abhisek as per question TC in best case also O(n^2)

because we can find correct position for element in logn time.. but after inserting the element we need to adjust the array so finally it takes O(n)

@Arjun @srestha @talha hashim @MiNiPanda

My Question sounds lame but plz explain how we can use Binary search here when we know it can be applied on Sorted sequences only.? I mean what is question intending to say.?

(Plz refer to that point if this is already being answered.?)

@SomeEarth binary search is used only to insert the current element in insertion sort. And all elements before the current element are sorted in Insertion sort.

For each element we need to find its position in the sorted part using binary search and then place the element in its correct position by swapping.

(Below I have taken sum, taking into consideration each iteration of insertion sort)

Worst case time complexity for binary search (taking all iterations into consideration)= log 1 + log 2 + log 3 + ... + log (n-1) + log (n) = log($1\times2\times3...\times(n-1)\times(n)$) = log n! = $\Theta(n log n)$ .(There is a nice proof for this here.)

Worst case time complexity for swaps (taking all iterations into consideration) = 1 + 2 + 3 + ... + (n-1) + (n) = $\frac{n\times(n+1)}{2}$ = $\Theta(n^{2})$

Total time complexity including swaps and binary search = $\Theta(n log n)$ + $\Theta(n^{2})$ = $\Theta(n^{2})$

**A**. Complexity remains same.*θ*(*n*^{2})

To place the element x in the correct position first we are finding its correct position in the sorted array using binary search but we have to make the space for it by shifting all elements to the right, which in worst case may be equal to the size of the sorted array.