title: What is the complexity of this nested triple for loop?
body: <p>I have searched a bit on StackOverflow and have understood the complexity up to the point of the j-loop, which is <code>O(n<sup>2</sup>)</code>. However with the nested addition of the k-loop, I am confused as why the complexity becomes <code>O(n<sup>3</sup>)</code>. Can someone help me understand this?</p>
  
  <p>From my understanding, the i-loop have n iterations and the j-loop have 1+2+3+...+n iterations <code>n*(n+1)/2</code> which is <code>O(n<sup>2</sup>)</code>.</p>
  
  <pre><code>for(i = 1; i &lt; n; i++) {   
      for(j = i+1; j &lt;= n; j++) {
          for(k = i; k &lt;= j; k++) {
             // Do something here...
          }
      }
  }
  </code></pre>
  
  <p><strong>EDIT:</strong> Thanks for all your help guys :) Balthazar, I have written a piece of code to which will increment counters depending on which loop they are in, kinda a crude way of step-by-step:</p>
  
  <pre><code>#include &lt;iostream&gt;
  
  int main(int argc, const char * argv[])
  {
      int n = 9;
      int index_I = 0;
      int index_J = 0;
      int index_K = 0;
      for (int i = 1; i &lt; n; i++) {
          for (int j = i+1; j &lt;= n; j++) {
              for (int k = i; k &lt;= j; k++) {
                  index_K++;
              }
              index_J++;
          }
          index_I++;
      }
      std::cout &lt;&lt; index_I &lt;&lt; std::endl;
      std::cout &lt;&lt; index_J &lt;&lt; std::endl;
      std::cout &lt;&lt; index_K &lt;&lt; std::endl;
      return 0;
  }
  </code></pre>
  
  <p>I ran this code from n=2 to n=9 with increments of 1 and have got the following sequence:</p>
  
  <p><img src="https://i.stack.imgur.com/iRSwa.png" alt=""></p>
  
  <p>From the counters, it can therefore be seen that:
  i = n-1 giving the complexity of O(n) and j = ((n-1)*n)/2 giving the complexity <code>O(n<sup>2</sup>)</code>. A pattern for K was hard to spot but it is known that K depends on J, therefore:</p>
  
  <p><img src="https://i.stack.imgur.com/ZGWin.png" alt=""></p>
  
  <p><code>k = ((n+4)/3)*j = (n*(n-1)*(n+4))/6</code> giving a complexity of <code>O(n<sup>3</sup>)</code></p>
  
  <p>I hope this will help people in the future.</p>
  
  <p>EDIT2: thanks <a href="https://stackoverflow.com/users/1711796/dukeling">Dukeling</a> for the formatting :) Also found a mistake in the last line, corrected now</p>