GATE Exam | Aptitude Questions | GATE Syllabus | GATE Result | Mock Test | GATE Preparation
0 votes

What is the worst case time complexity of insertion sort where position of the data to be inserted is calculated using binary search?

A

N

B

NlogN

C

N^2

D

N(logN)^2

asked in Searching, sorting by gate

2 Answers

0 votes
C

N^2

Applying binary search to calculate the position of the data to be inserted doesn't reduce the time complexity of insertion sort. This is because insertion of a data at an appropriate position involves two steps: 1. Calculate the position. 2. Shift the data from the position calculated in step
answered by gate
0 votes
The worst case complexity would be O(n^2) as binary search helps in searching the appropriate position in O(log(n)) time but the shifting has to be done in O(n^2)) time.
Mathematically,
T(n)= n^2 + log(n)
T(n)=n^2
answered by anonymous

Related questions

The best answer to any question