Calculating Running Time of Recurrence Relations

Question

I had to calculate the Running Time of the following Algorithm.

function Fib(n)
    if n == 0 or n == 1 then
        return 1
    else
        return Fib(n-1) + Fib(n-2)

Now I calculate it's running time to be about $O(2^n)$ I'm new to this subject so correct be if it's not $O(2^n)$. Now the questions asks if one wanted to calculate Fib(50) how many times would Fib(10) be called. I'm stumped at this part. I tried to make a diagram and calculate it through brute-force but I'm pretty sure there must be a much easier method to it.

Answer 1

If you draw the recursion tree for a few levels, you will find the pattern so you don't need to draw the whole tree and count the answer in a brute-force fashion:

From here, you know that $Fib(50)$ is called $1$ time, $Fib(49)$ is called $1$ time, $Fib(48)$ is called $2$ times, $Fib(47)$ is called $3$ times, $Fib(46)$ is called $5$ times. For $Fib(45)$, you can see $7$ occurrences here, but there will be an $8$th call, just below the lowest level that we have drawn (under the $Fib(46)$ in the bottom left corner). So $Fib(45)$ is called $8$ times. Let $T(n)$ be the number of times $Fib(n)$ is called, now you can see the pattern and generalize this relation:

$T(49) = T(50) = 1$

$T(n - 2) = T(n) + T(n - 1)$ for $1 \le n \le 48$

In other words, $T(n)$ is the $(51-n)$-th Fibonacci number. So you can now find $T(10)$.

Added: In fact, the recursion tree diagram can also help understand why the overall complexity is $O(2^n)$. $Fib(n)$ only appears on or above Level $(50-n)$ of the tree (assume the root is Level $0$), so when $n$ increases by $1$, the height of the tree increases by $1$ as well. And this causes the number of calls to be approximately doubled. Hence the overall time complexity is $O(2^n)$.

Answer 2

It is not $O(n)$.

If $T(n)$ is the number of calls to Fib(10) when computing $\text{Fib}(n)$, then $T(n) = 0$ for $n < 10$, $T(10) = 1$, $T(n) = T(n-1) + T(n-2)$ for $n > 10$.

Hint: consider $g(n) = T(n+9)$.