# Does this version of insertion sort have O(n) complexity for best case?

``````for ( i = 1 ; i <= N ; i++ )
{
for ( j = 0 ; j < i ; j++ )
{
if ( arr[j] > arr[i] )
{
temp = arr[j] ;
arr[j] = arr[i] ;

for ( k = i ; k > j ; k-- )
arr[k] = arr[k - 1] ;

arr[k + 1] = temp ;
}
}
}
``````

If not, can it really be called insertion sort? This version of sort is there in a book from reputed author originally.

-
Looks like O(3N + 7) to me as a first order approximation. I would thus say it has O(n) complexity ignoring the constant term. – Mushy Apr 4 '13 at 11:23
no it has at least O(n^2) because you never exit the inner loop prematurely – ratchet freak Apr 4 '13 at 11:24
Can you share how best case(nearly sorted array) has 3N+5 comparisons? It looks like there will be approximately 1+2+3+4+...+N = N(N+1)/2 = (N^2+N)/2 comparisons which is O(N^2) – amitamb Apr 4 '13 at 11:31

The best case occurs when the if statement never gets entered. Then we just have to count the number of times we evaluate the condition of the if statement to determine that we don't want to do it.

The outer loop ranges i from 1 to N and the inner ranges j from 0 to i. Let's count the number of times we check that if-condition:

``````At i = 1  we look at j 1 times  (at j = 0)
At i = 2  we look at j 2 times  (at j = 0, 1)
At i = 3  we look at j 3 times  (at j - 0, 1, 2)
At i = 4  we look at j 4 times  (at j - 0, 1, 2, 3)
At i = 5  we look at j 5 times

At i = N-1  we look at j N times   (at j - 0, 1, 2, ... N-1)
``````

This is the classic 1+2+3+4+....+N arithmetic series known to be O(N^2).

It is not insertion sort. Real insertion sort is O(N) in the best case.

I don't know what this algorithm is.

-
This does look like an insertion sort. It's just missing break inside that if statement, and then it would have O(N) complexity for arrays that are already sorted in reversed order. – Piotr Kalinowski Apr 4 '13 at 14:55
You're right: it acts like insertion sort (though unusual in the j loop), but with a good deal of redundant checking. But there is really no reason to structure the algorithm with three nested loops. Two loops certainly suffice and the algorithm can be written very cleanly with just two. There do exist sorting algorithms with extra and useless computations, such as StupidSort, StoogeSort, BozoSort, BogoSort, etc. that do silly things. This algorithm I'm sure wasn't intended to be a purposely inefficient like the ones I just mentioned, but I thought it might nevertheless be named.... – Ray Toal Apr 5 '13 at 4:41

Assuming it's already sorted, that `if` statement never gets entered. So you have two loops through everything and it'll execute in n^2 time.

But that's not "Big-O". Big-O cares about the worst time, not the best. I believe this algorithm is O(n^3). The inner loops only execute n/2 and ... I think n/3, but all that division gets thrown away when talking about Big-O.

It's been awhile but I think the best case scenario is called "big omega".

-
Lower bounds (best case) is Big Omega, Upper bounds is Big O, approximate is Tilde and the growth rate is Big Theta. If I remember correctly. – Jeroen Vannevel Apr 4 '13 at 14:09