retagged by
799 views
2 votes
2 votes

I answered this as $O(n^2)$ considering the question asks for best worst case of all inplace sorting algorithms.

retagged by

2 Answers

1 votes
1 votes

O(n) is right 

BEST CASE OF INSERTION SORT

The best case input is an array that is already sorted. In this case insertion sort has a linear running time (i.e., O(n)). During each iteration, the first remaining element of the input is only compared with the right-most element of the sorted subsection of the array.

1 votes
1 votes

Bubble sort, as well as Insertion sort both, will give o(n) in its best case: in bubble sort assumption is made that the passes will be stopped on the same instance when the elements are sorted. While in Insertion sort assumption is that the elements are already sorted or almost sorted

Related questions

0 votes
0 votes
2 answers
1
2 votes
2 votes
1 answer
2
Raj_Choudhary asked Nov 22, 2017
592 views
Suppose in an array A[] , we exchange elements A[i] and A[i+k] , which were originally out of orderA) at least 1 and at most 2k-1 inversions are removedB) at least 2 and ...
0 votes
0 votes
2 answers
4
_Madhuri asked Oct 9, 2021
631 views
The complexity of comparison based sorting algorithm is (nlogn) .How?