title: Why best case for insertion sort is O(n) & not O(n^2)?
body: <p>I am having a hard time understanding why best case of insertion sort in o(n) ?</p>
  
  <pre><code>     for (int i = 0; i &lt; size; i++) {
  
                  for (int j = i; j &gt; 0; j--) {
                      int k = j-1;
                          if( a[j] &lt; a[k]){
                              int temp = a[j];
                              a[j] = a[k];
                              a[k] = temp;
                          }
  
                  }
       }
  </code></pre>
  
  <p>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, &amp; it will be exactly equal as unsorted array ?
  then n-1 (outer loop) * n - 1(inner loop) = n^2 - n + 1 = O(n^2)<br>
  can any one explain me where i m wrong ?</p>