title: Time complexity for all Fibonacci numbers from 0 to n
body: <p>I was calculating the time complexity of this code that prints all Fibonacci numbers from 0 to n. According to what I calculated, the <code>fib()</code> method takes <code>O(2^n)</code> and since it is being called <code>i</code> number of times, so it came out to be <code>O(n*2^n)</code>. However, the book says it is <code>O(2^n)</code>. Can anyone explain why the time complexity here will be <code>O(2^n)</code>?</p>
  
  <p>Here is the code:</p>
  
  <pre><code>void allFib(int n){
      for(int i = 0 ; i &lt; n ; i++){
          System.out.println(i + ": " + fib(i));
      }
  }
  
  int fib(int n ){
      if(n &lt;= 0) return 0;
      else if (n == 1) return 1;
      return fib(n-1) + fib(n-2);
  }
  </code></pre>