The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+29 votes

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)$

+46 votes

Best answer

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.**

0

why you have take it for n elements. there is nothing specified for number of elements. please explain.

0

@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.

+21 votes

**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.

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,873 questions

47,534 answers

146,071 comments

62,300 users