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

By induction: if calculation of fib(k) takes less than C*2^k for all k < n, for the calculation tome of fib(n) we've got

T(n) = T(n-1) + T(n-2) + K < C*2^(n-1) + С*2^(n-2) + K
     = 0.75*C*2^n + K < C*2^n

for sufficiently big C (for C > K/0.25, as 2^n > 1). This proves that T(n) < C*2^n, i.e. T(n) = O(2^n).

(Here T(n) is the time for calculation of fib(n), K is the constant time needed for calculating fib(n) when both fib(n-1) and fib(b-1) are [already] calculated.)

Answer 2

You need to solve the recurrence equation:

T(0) = 1
T(1) = 1
T(n) = T(n-1) + T(n-2), for all n > 1

Answer 3

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 is 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. n).

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)