title: running time of 3 nested loops
body: <p>I am quite confused on whether this alogrithm has a running time of <code>O(n^2)</code> or <code>O(n^3)</code>. The program looks like this:</p>
  
  <pre><code>int count=0;
  
  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++){
              count++;
          }
      }
  }
  
  System.out.print("count: " + count);
  </code></pre>
  
  <p>I used an example of <code>n=7</code>. This gave me a result (count) of <code>35</code>. I know that the i and j loops together has the running time of the gaussian sum, which is <code>1+2+3...n=O(n^2)</code>. I tried to figure out the full running time of all 3 loops by doing some calculations.
  I used the Gauss sum formula given by: <a href="https://i.stack.imgur.com/sorju.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/sorju.png" alt="enter image description here"></a></p>
  
  <p>I figured out that making gaussian sums and adding them up gives me the correct result.(starting from <code>i=2</code> until <code>i=n-1</code>) The formula I got to was:</p>
  
  <p><a href="https://i.stack.imgur.com/BUfLa.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/BUfLa.png" alt="enter image description here"></a></p>
  
  <p>How would I remove the summation sign and get a regular "formula"? </p>
  
  <p>Thank you for your time! </p>