Algorithms

Question

1. The usual Θ(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 (GATE CS 2003)
(a) remain Θ(n^2)
(b) become Θ(n(log n)^2)
(c) become Θ(n log n)
(d) become Θ(n)

Ans is (a) Pls explain why is it a becaue i think the answer should be (c)

Comments

we need to take care about swapping + comparision time

here comparision time reduced but swapping time remains same

so ans is right

Answer 1

The main reason u think this way is you are ignoring Swaping .

Take example = 6, 5, 4, 3, 2 ,1

since u find correct place using inersion sort then when u have to swap n-1 element in worst case.

place 6

place 5, 6 here one comparision and 1 swap

 place 4, 5, 6 here two comparision and 2 swap( 5 comes at place of 6 and 65 shift right)

 place 3, 4, 5, 6 here two comparision and 3 swap ...

in this way have to swap n-1 element for every insersion which take 1 + 2+3+4+5...=  $n^2$

So total time  = swap time +  comparision

                     = $n^2$ + $nlogn$

                     = O($n^2$)

Comments

Thanx! Got it