title: Computational complexity of Fibonacci Sequence
body: <p>I understand Big-O notation, but I don't know how to calculate it for many functions. In particular, I've been trying to figure out the computational complexity of the naive version of the Fibonacci sequence:</p>
  
  <pre><code>int Fibonacci(int n)
  {
      if (n &lt;= 1)
          return n;
      else
          return Fibonacci(n - 1) + Fibonacci(n - 2);
  }
  </code></pre>
  
  <p>What is the computational complexity of the Fibonacci sequence and how is it calculated?</p>