title: Calculating Time Complexity.. Need help coming up with the end result
body: <p>Studying for a midterm tomorrow, and these time complexities are something I struggle with.  I'm going over the simple examples in the book and for this example</p>
  
  <p><strong>Exchange Sort</strong></p>
  
  <pre><code>void exchangesort (int n, keytype S[])
  {
    index i, j;
    for(i=1; i&lt;=n-1; i++)
      for(j=i+1; j&lt;=n; j++)
        if(S[j] &lt; S[i])
          exchange S[i] and S[j];
  }
  </code></pre>
  
  <p>For the "Every-Case Time Complexity" of this Exchange sort, I understand the part that we pretty much analyze the <code>j</code> for-loop, because it has the basic operation (the exchange). And so if you list out the total number of passes, it's given by:</p>
  
  <pre><code>T(n) = (n-1) + (n-2) + (n-3) + ... + 1 = (n-1)n/2
  </code></pre>
  
  <p>Now my question is... where does the 1 come from?  I thought it was <code>n-1 + n-2 +... + n</code>.</p>
  
  <p>Furthermore, what I really don't understand is how to come up with the <code>(n-1)n/2</code>.<br>
  That's obviously what I have to come up with in the midterm, and by looking at that, <code>(n-1)n/2</code> doesn't come intuitively...  I understand how to come up with the <code>T(n) = (n-1) + (n-2)</code> etc., I think...</p>
  
  <p>Can someone explain this to me in laymen's terms so I can come up with an answer like this for my midterm tomorrow?</p>