title: Complexity of triple-nested Loop
body: <p>I have the following algorithm to find all triples</p>
  
  <pre><code>for (int i = 0; i &lt; N; i++)
      for (int j = i+1; j &lt; N; j++)
           for (int k = j+1; k &lt; N; k++)
               if (a[i] + a[j] + a[k] == 0)
                  { cnt++; }
  </code></pre>
  
  <p>I now that I have triple loop and I check all triples. How to show that the number of different triples that can be chosen from N items is precisely <code>N*(N-1)*(N-2)/6</code> ?</p>
  
  <p>If we have two loops</p>
  
  <pre><code>for (int i = 0; i &lt; N; i++)
      for (int j = i+1; j &lt; N; j++)
               ...
  </code></pre>
  
  <p>when <code>i = 0</code> we go to the second loop <code>N-1</code> times</p>
  
  <p><code>i = 1</code> => <code>N-2</code> times</p>
  
  <p>...</p>
  
  <p><code>i = N-1</code> => 1 time </p>
  
  <p><code>i = N</code> => 0 time </p>
  
  <p>So <code>0 + 1 + 2 + 3 + ... + N-2 + N-1 = ((0 + N-1)/2)*N = N*N - N/2</code></p>
  
  <p>But how to do the same proof with triples?</p>