What is the worst case time complexity of insertion sort? (i.e number of comparisons?)
2(n log n)
With the first outer loop, in the sort() function, we will call
embed() function, where it is comparing 1 time.
second outer loop, in sort() function, we will call embed()
function, where it is comparing 2 times.
In the last loop, it compares n-1 times.
So total no of comparisons are (worst case):
1+2+...+(n-2)+(n-1) = (n-1)(n/2) = n^2
Back To Top