Getting a tighter upper bound on the following function

Question

We have the following function which determines the Nth fibonacci number:

int fib(int n){
    if(n<=0) return 0;
    else if (n==1) return 1;
    return fib(n-1)+ fib(n-2)

}

Find the time complexity

I am currently reading the book "Cracking the coding interview" and the answer it gave is quite disappointing. The book says that there are 2 branches per call, and we go as deep as N, therefore the runtime is $O(2^N)$ and it later explains that a tighter upper-bound is $O(1.6^N)$, but it doesn't go over it because the mathematics are "very complex. It doesn't even point out the place where we can find the approach to get the desired upper-bound. I don't want to defame "cracking the coding interview", but I think that more consistency must be shown. My question is, how do we get $O(1.6^N)$ for the algorithm?. It doesn't look like top notch math.

Answer 1

Let's count how many times we have to make a call into fib for each value of n. Let's call that number $f(n)$.

Then:

$$ \begin{align} f(0) &= 1 \\ f(1) &= 1 \\ f(n) &= 1 + f(n-1) + f(n-2) \qquad \textrm{(for $n > 1$)} \end{align} $$

The first several values for $f$ are then 1, 1, 3, 5, 9, 15, 25, 41, 67, etc.

It turns out that if you add one to $f$ and half the result,(*) you get the sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, etc.

That is, $f(n) = 2\cdot\textrm{fib}(n+1) - 1$

Since it is well known that the Fibonacci function is $O\left((\frac{1+\sqrt{5}}{2})^n\right)$, so is $f(n)$.

Note that since $\frac{1+\sqrt{5}}{2} \approx 1.618 > 1.6$, the book is actually technically incorrect when it says that $O(1.6^N)$ is an upper bound, and should be corrected to say $O(1.62^N)$ or something similar.

---

(*) Okay, I kind of pull that out of a hat. As for how to mentally jump from a recursion that's almost like one you know but off by a constant (as in this case, the recursion formula for $f$ looked like the recursion for fib but had that annoying $1+$ at the beginning) one technique is to say:

"What if $g$ were something that obeyed fib's recursion rule, and $f(n) = g(n) + C$ for some constant $C$. What happens when I substitute that into my recursion equation?"

You then end up with:

$$ g(n) + C = 1 + g(n-1) + C + g(n-2) + C $$

Using $g(n) = g(n-1) + g(n-2)$, you find that $C$ is $-1$. From that you see "Oh, $1+f(n)$ should look kind of like the Fibonacci series, but it starts with "2, 2", so..." (and then it's straightforward to write a formula for $f(n)$).