title: Big-O for various Fibonacci Implementations
body: <p>I just tried implementing code (in Java) for various means by which the nth term of the Fibonacci sequence can be computed and I'm hoping to verify what I've learnt.</p>
  
  <p>The iterative implementation is as follows:</p>
  
  <pre><code>public int iterativeFibonacci(int n)
  {
    if ( n == 1 ) return 0;
    else if ( n == 2 ) return 1;
    int i = 0, j = 1, sum = 0;
    for ( ; (n-2) != 0; --n )
    {
      sum = i + j;
      i = j;
      j = sum;
    }
    return sum;
  }
  </code></pre>
  
  <p>The recursive implementation is as follows :-</p>
  
  <pre><code>  public int recursiveFibonacci(int n)
    {
      if ( n == 1 ) return 0;
      else if ( n == 2 ) return 1;
      return recursiveFibonacci(n-1) + recursiveFibonacci(n-2);
    }
  </code></pre>
  
  <p>The memoized implementation is as follows :-</p>
  
  <pre><code>  public int memoizedFibonacci(int n)
    {
      if ( n &lt;= 0 ) return -1;
      else if ( n == 1 ) return 0;
      else if ( n == 2 ) return 1;
      if ( memory[n-1] == 0 )
        memory[n-1] = memoizedFibonacci(n-1);
      if ( memory[n-2] == 0 )
        memory[n-2] = memoizedFibonacci(n-2);
      return memory[n-1]+memory[n-2];
    }
  </code></pre>
  
  <p>I'm having a bit of a doubt when trying to figure out the Big-O of these implementations. I believe the <em>iterative implementation to be O(n)</em> as it loops through N-2 times.</p>
  
  <p>In the recursive function, there are values recomputed, hence I think it's <em>O(n^2)</em>.</p>
  
  <p>In the memoized function, more than half of the values are accessed based on memoization. I've read that <em>an algorithm is O(log N) if it takes constant time to reduce the problem space by a fraction</em> and that <em>an algorithm is O(N) if it takes constant time to reduce the problem space by a constant amount</em>. Am I right in believing that the memoized implementation is <em>O(n)</em> in complexity? If so, wouldn't the iterative implementation be the best among all three? (as it does not use the additional memory that memoization requires).</p>