title: What is the space complexity of this algorithm (n or log(n))?
body: <p>I have a question regarding the space (memory) complexity of this particular piece of pseudocode:</p>
  
  <pre><code>int b(int n, int x) {
     int sol = x;
     if (n&gt;1) {
        for (int i = 1; i &lt;= n; i++) {
           sol = sol+i;
        }
        for (int k=0; k&lt;3; k++) {
           sol = sol + b(n/3,sol/9);
        }
     }
     return sol;
  }
  </code></pre>
  
  <p>The code gets called: <code>b(n,0)</code></p>
  
  <p>My opinion is, that the space complexity progresses linearly, that is <code>n</code>, because as the input <code>n</code> grows, so does the amount of variable declarations (<code>sol</code>).</p>
  
  <p>Whereas a friend of mine insists it must be <code>log(n)</code>. I didn't quite get his explanation. But he said something about the second <code>for</code> loop and that the three recursive calls happen in sequence.</p>
  
  <p>So, is <code>n</code> or <code>log(n)</code> correct?</p>