title: Space Complexity and Auxilary space for iterative code below>>>>
body: <pre><code>int fib(int n){   // let n = 4;
    int f[n+1];     // array length becomes 5
    f[0] = 0;         
    f[1] = 1;
    for(int i = 2 ; i &lt;= n ; i++ ){
       f[i] = f[i-1] + f[i-2];
    }
    return f[n];    
  }
  </code></pre>
  <p>Now, The Time Complexity of this program is coming out to be O(n) or Theta(n) But, what will be the Space Complexity and Auxilary space?</p>
  <p>For results on internet it showing SC = theta(n) and aux space also thetha(n) but how??</p>
  <p>if we see that the space created by us for fibonacci series is (n+1) so by removing constant the Aux space becomes theta(n) but the space Complexity (by my calculation) is thetha(1) because this program taking an integer as input and giving back an integer as output so it come up to be constant i.e. Theta(1), but every where it is theta(n) How? Please Explain&gt;&gt;&gt;</p>
  <p><a href="https://i.stack.imgur.com/ck8nw.jpg" rel="nofollow noreferrer">Visualization solution for this problem is it correct??</a></p>