Why best case for insertion sort is O(n) & not O(n^2)?

Question

I am having a hard time understanding why best case of insertion sort in o(n) ?

     for (int i = 0; i < size; i++) {

                for (int j = i; j > 0; j--) {
                    int k = j-1;
                        if( a[j] < a[k]){
                            int temp = a[j];
                            a[j] = a[k];
                            a[k] = temp;
                        }

                }
     }

Lets consider an example initial array [1,2,3,4,5] size = 5 first loop will go from i = 0 to size - 1 and second loop will go from i to 1 but lets assume, inner for loop also goes from 0 to size - 1 in other words inner for loop also executes (n-1) times similar to outer for loop I agree there will be no swaps but there will be Comparison's, & it will be exactly equal as unsorted array ? then n-1 (outer loop) * n - 1(inner loop) = n^2 - n + 1 = O(n^2)
can any one explain me where i m wrong ?

Answer 1

Your code always runs in O(n^2). You have to break the inner for loop at the time you have found the place where the element should be.

Answer 2

Consider the following implementation of insertion sort:

    for (i=1; i<n; i++) {
        j=i;
        while ((j>0) && (s[j] < s[j-1])) {
            swap(&s[j],&s[j-1]);
            j = j-1;
        }
    }

The best case for any sorting algorithm is when input is already in sorted order. Here in such scenario, the condition at while loop always returns false and hence it only iterates for the outer for loop, doing the job in linear time with O(n) time complexity.

Answer 3

At first, this does not seem to be a proper code for insertion sort. It seems that you are using bubble sort code in reverse manner.
In an insertion sort code you don't replace a small element with every large element that falls before it, rather we skim through all the large elements that fall before it and only when we are at the point where there are no elements left or there is no more large element, then we place the small element at that place and shift/move all other succeeding elements.

As a part for O(n) time:
Lets consider an array of five already sorted elements - arr[11,13,15,17,19]. We move from first position element to last position.
Step 1: Take element 11, as it is first element we keep it as it is.
Step 2: Take element 13, look for element that falls before it(that is element 11), as 13>11, therefore no further need for looking at elements that fall before 11.
Step 3: Take element 15, look for element that falls before it(that is element 13), as 15>13, therefore no further need for looking at elements that fall before 13.
Step 4: Take element 17, look for element that falls before it(that is element 15), as 17>15, therefore no further need for looking at elements that fall before 15.
Step 5: Take element 19, look for element that falls before it(that is element 17), as 19>17, therefore no further need for looking at elements that fall before 17.

As we see that for five already sorted elements we required only 5 comparisons, thus for 'n' sorted elements we require only O(n) comparisons.

I hope above example clarifies your doubt.