title: Solving Recursion in fibonacci numbers
body: <p>I'm unaware of the mathematics in this algorithm and could use some help. </p>
  
  <p>Algorithm:</p>
  
  <pre><code>if n&lt;2 then
  
    return n
  
  else return fibonacci(n-1) + fibonacci(n-2)
  </code></pre>
  
  <p>Statement                     </p>
  
  <p>n &lt; 2 is O(1)<br>
  Time n >=2 is O(1)<br>
  Return n is O(1)
  Time n>=2 is -
  Return fib(n-1) + fib(n-2) is - </p>
  
  <p>and time n>=2 is T(n-1) + T(n-2) +O(1)  </p>
  
  <p>Total: O(1) T(n-1) + T(n-2) + O(1)<br>
  T(n) =  O(1) if n &lt; 2<br>
  T(n) = T(n-1) + T(n-2) + O(1) if n>=2  </p>