Number of calls for nth Fibonacci number


Question

Consider the following code snippet:

int fib(int N)
{
   if(N<2) return 1;
   return (fib(N-1) + fib(N-2));
}

Given that fib is called from main with N as 10,35,67,... (say), how many total calls are made to fib?

Is there any relation for this problem?

PS: This is a theoretical question and not supposed to be executed.

EDIT:

I am aware of other methods for the faster computation of Fibonacci series.

I want a solution for computing number of times fib is invoked for fib(40),fib(50) ,.. without the aid of compiler and in exam condition where you are supposed to answer 40 question similar to this one in a stipulated of time ( about 30 mints).

Thanks,

1
8
11/28/2009 11:35:16 AM

Let f(n) be the number of calls made to calculate fib(n).

  • If n < 2 then f(n) = 1.
  • Otherwise, f(n) = 1 + f(n - 1) + f(n - 2).

So, f is at least O(fib(n)). In fact, f(n) is 2 * fib(n) - 1. We show this by induction:

  • Base cases (n < 2, that is, n = 0 or n = 1):
    • f(n) = 1 = 2 * 1 - 1 = 2 * fib(n) - 1.
  • Induction step (n >= 2):
    • f(n + 1) = f(n) + f(n - 1) + 1
    • f(n + 1) = 2 * fib(n) - 1 + 2 * fib(n - 1) - 1 + 1
    • f(n + 1) = 2 * fib(n + 1) - 1

There exist efficient ways to calculate any Fibonacci term. Thus the same holds for f(n).

11
11/15/2009 11:23:46 PM

Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon