title: Formula for Nested Loops with Dependence
body: <blockquote>
    <p><strong>Possible Duplicate:</strong><br>
    <a href="https://stackoverflow.com/questions/12326708/big-o-nested-for-loop-with-dependence">Big O: Nested For Loop With Dependence</a>  </p>
  </blockquote>
  
  
  
  <p>Given the following nested loops, I have to figure out the Big O complexity of it:</p>
  
  <pre><code>for(i=0 to n)
      for(j=n-1;j&gt;=i;j--)
  </code></pre>
  
  <p>I know that the complexity of this will be <code>O(n^2)</code>, but I am unsure of how to figure out the formula for the inner loop.</p>
  
  <p>I wrote out a table, for clarity:</p>
  
  <pre><code>n=10
  i | j | outer iters | inner iters
  0 | 9 |     1       |     10
  1 | 9 |     2       |      9 
  ...
  9 | 9 |    10       |      1
  </code></pre>
  
  <p>Therefore, the outer loop runs <code>n</code> times, while the inner runs <code>sum(n to n-9)</code>.</p>
  
  <p>I was told the answer was <code>n(n-2)/2</code>, and I simply can't figure out how to get from what I have, to this conclusion.</p>
  
  <p>Assistance would be greatly appreciated.</p>