edited by
607 views
0 votes
0 votes
"The running time of insertion sort is not Ω($n^{2}$) , since there exists an input for which insertion sort runs in  $\Theta (n)$. It is not contradictory , however , to say that the worst case running time of insertion sort is Ω($n^{2}$) " .

Could anyone explain this line ?
edited by

Please log in or register to answer this question.

Related questions

2 votes
2 votes
1 answer
2
dragonball asked Oct 21, 2017
1,124 views
Wha is the relationship between the running time of insertion sort and the number of inversions in the input array ?Is the circled text should be greater instead of less ...
0 votes
0 votes
1 answer
3
dragonball asked Jun 22, 2017
369 views
While solving this recurrence T(n) = 2T(n/2 + 17) + n what is the need of 17 and how to go forward to solve this question using the method of master theorem ?
0 votes
0 votes
1 answer
4
Neha_16 asked Apr 27, 2018
5,806 views
Use a recursion tree to give an asymptotically tight solution to the recurrenceT(n) =T(an)+T((1-a)n)+cn, where a is constant in the range 0<a<1 and c>0 is also a constant...