title: why is Insertion sort best case big O complexity O(n)?
body: <p>Following is my insertion sort code:</p>
  
  <pre><code>void InsertionSort(vector&lt;int&gt; &amp; ioList)
  {
    int n = ioList.size();
    for (int i = 1 ; i &lt; n ; ++i)
    {
      for (int j = 0 ; j &lt;= i ; ++j)
      {
        //Shift elements if needed(insert at correct loc)
        if (ioList[j] &gt; ioList[i]) 
        {
          int temp = ioList[j];
          ioList[j] = ioList[i];
          ioList[i] = temp;
        }
      }
    }
  }
  </code></pre>
  
  <p>The average complexity of the algorithm is O(n^2). </p>
  
  <p>From my understanding of big O notation, this is because we run two loops in this case(outer one n-1 times and inner one 1,2,...n-1 = n(n-1)/2 times and thus the resulting asymptomatic complexity of the algorithm is O(n^2).</p>
  
  <p>Now I have read that best case is the case when the input array is already sorted.
  And the big O complexity of the algorithm is O(n) in such a case. But I fail to understand how this is possible as in both cases (average and best case) we have to run the loops the same number of times and have to compare the elements. The only thing that is avoided is the  shifting of elements. </p>
  
  <p>So does complexity calculation also involve a component of this swapping operation?</p>