title: How to calculate the theoretical running time of insertion sort, for any input n?
body: <p>Note that I'm using insertion sort as an example, here. I've been given an assignment in my C.S. class which involves comparing the resulting run-times of various sorting algorithms with the <em>theoretical run-times</em> which should occur.</p>
  
  <p>For example, let's say I have an input array of 1000 randomly ordered integers, and I'm operating under the assumption of a worst-case scenario. The result may be somewhere around <code>320.x milliseconds</code>. Yet, theoretically, it should be a flat <code>300 milliseconds</code>. Likewise, if I bump up the input size to 6000, I could get <code>11,735.577106 milliseconds</code> (as shown in the example provided by my C.S. teacher); the theoretical running time, however, would be <code>10,800 milliseconds</code>.</p>
  
  <p>We know that worst-case performance of insertion-sort is <code>f(n) = O(n^2)</code>. Not aware of the original definition of <code>f</code>, I looked it up and found the result to be,</p>
  
  <p><code>f(n) = ( n(n - 1) + n ) / 2 = n^2 / 2</code>.</p>
  
  <p>Which leads me to the recurrence relation for the algorithm:</p>
  
  <p><code>T(n) = T(n-1) + f(n)</code></p>
  
  <p>So, I decided to write a little C program and test <code>T(n)</code> with an input of 1000, expecting to get around 300000 or so.</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  
  // Recurrence relation for insertion sort ( worst-case )
  float T( float n )
  {
      if ( n == 1.0f )
          return 1.0f;
  
      return T( n - 1 ) + n * n * 0.5f;
  }
  
  int main( void )
  {
      printf( "T( %f ) = %f \n", 1000.0f, T( 1000.0f ) );
  
      return 0;
  }
  </code></pre>
  
  <p>Output:</p>
  
  <pre><code>T( 1000.000000 ) = 166916608.000000
  </code></pre>
  
  <p>Clearly, this wasn't the case.</p>
  
  <p>So, I'm stumped.</p>
  
  <p><strong>tl;dr</strong></p>
  
  <p><em>I'd like to know how my professor arrived at 300 milliseconds for a theoretical run-time, using an insertion sort of an array of 1000 elements. My understanding is that recurrence relations are used to solve this, yet the output of the code shown (which is supposed to be the recurrence relation of insertion sort's worst-case) doesn't provide any clear means of easily understanding how this actually is computed.</em></p>