title: Two inner nested loop run time
body: <pre><code>void smiley (int n) { 
  
   for (int i = 0; i &lt; n * n; ++i) { 
      for (int k = 0; k &lt; i; ++k) 
        System.out.println(”k = ” + k); 
      for (int j = n; j &gt; 0; j--) 
        System.out.println(”j = ” + j); 
     } 
  } 
  </code></pre>
  
  <p>As you can see, there are two inner loops and one outer loop. The run time for this is <code>n^4</code>. I get <code>n * n</code> makes it <code>n^2</code>, but how does the two inner loops make the total run time <code>n^4</code>?</p>
  
  <p>PS</p>
  
  <p>One similar case here, its run time is <code>n^2</code>. I also don't get it. It has three loops right?</p>
  
  <pre><code>void smiley (int n, int sum) { 
   for (int i = 0; i &lt; n * 100; ++i) { 
      for (int j = n; j &gt; 0; j--) 
         sum++; 
      for (int k = 0; k &lt; i; ++k) 
         sum++; 
      } 
  } 
  </code></pre>