title: Finding the time complexity of a recursive algorithm with a double for loop
body: <p>I am trying to find the tightest upper bound for the following upper bound. However, I am not able to get the correct answer. The algorithm is as follows:</p>
  <pre class="lang-cpp prettyprint-override"><code>public staticintrecursiveloopy(int n){
      for(int i = 0; i &lt; n; i++) {
          for(int j = 0; j &lt; n; j++) {
              System.out.println(&quot;Hello.&quot;);
          }
      } if(n &lt;= 2) {
          return 1;
      } else if(n % 2 == 0) {
          return(staticintrecursiveloopy(n+1));
      } else{
          return(staticintrecursiveloopy(n-2));
      }
  }
  </code></pre>
  <p>I tried to draw out the recursion tree for this. I know that for each run of the algorithm the time complexity will be O(n<sup>2</sup>) plus the time taken for each of the recursive calls. Also, the recursion tree will have n levels. I then calculated the total time taken for each level:</p>
  <p>For the first level, the time taken will be n<sup>2</sup>. For the second level, since there are two recursive calls, the time taken will be 2n<sup>2</sup>. For the third level, the time taken will be 4n <sup>2</sup> and so on until n becomes &lt;= 2.</p>
  <p>Thus, the time complexity should be n<sup>2</sup> * (1 + 2 + 4 + .... + 2<sup>n</sup>). 1 + 2 + 4 + .... + 2<sup>n</sup> is a geometric sequence and its sum is equal to 2<sup>n</sup> - 1.Thus, the total time complexity should be O(2<sup>n</sup>n<sup>2</sup>). However, the answer says O(n<sup>3</sup>). What am I doing wrong?</p>