0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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)$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.