An answer to this question on Stack Overflow.

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

Here's one way to implement insertion sort.

Take an input list and an initially-empty output list.

Iterate through the input list and place each item to its appropriate position on the output list. Find the appropriate position by walking through the output list, starting at the first element.

Now, if your input is already sorted, then the insertion point will always be at the beginning or end of the output list. The first possibility corresponds to the best-case scenario; the second corresponds to the worst-case scenario.

For example, my input data is: 4 3 2 1.

Then the output list builds as:

4
3 4
2 3 4
1 2 3 4

Since looking at the first element takes only O(1), then the time complexity is in the size of the input, or O(N).