Solving Recursion in fibonacci numbers

Question

I'm unaware of the mathematics in this algorithm and could use some help.

Algorithm:

if n<2 then

  return n

else return fibonacci(n-1) + fibonacci(n-2)

Statement

n < 2 is O(1)
Time n >=2 is O(1)
Return n is O(1) Time n>=2 is - Return fib(n-1) + fib(n-2) is -

and time n>=2 is T(n-1) + T(n-2) +O(1)

Total: O(1) T(n-1) + T(n-2) + O(1)
T(n) = O(1) if n < 2
T(n) = T(n-1) + T(n-2) + O(1) if n>=2

Answer 1

I think you're supposed to notice that the recurrence relation for this function is awfully familiar. You can learn exactly how fast this awfully familiar recurrence grows by looking it up by name.

However, if you fail to make the intuitive leap, you can try to bound the runtime using a simplified problem. Essentially, you modify the algorithm in ways guaranteed to increase the runtime while making it simpler. Then you figure out the runtime of the new algorithm, which gives you an upper bound.

For example, this algorithm must take longer and is simpler to analyze:

F(n): if n<2 then return n else return F(n-1) + F(n-1)