How many additional function calls does fib(n) require if "LINE 3" is removed?

I just got this ques开发者_如何学编程tion on an interview and had no idea how to calculate the answer.

How many additional function calls does fib(n) require if "LINE 3" is removed? The answer should be in terms on n.

int fib(int n) {
  if(n == 0) return 0;
  if(n == 1) return 1;
  if(n == 2) return 1; //LINE 3 HERE <---

  return fib(n - 1) + fib(n - 2);
}

It can be easily calculated. The old code:

TO(0)=TO(1)=TO(2)=1
TO(n)=TO(n-1)+TO(n+2)+1

The new code:

TN(0)=TN(1)=1
TN(n)=TN(n-1)+TN(n-2)+1

The difference is computed simply by subtracting those two:

D(0)=D(1)=0
D(2)=3-1=2
D(n)=TN(n)-TO(n)=TN(n-1)+TN(n-2)+1-(TO(n-1)+TO(n+2)+1)
    =(TN(n-1)-TO(n-1))+(TN(n-2)-TN(n-2))+(1-1)
    =D(n-1)+D(n-2)

Which means the difference is a Fibonacci sequence beginning with 0,0,2. It is also possible to calculate a closed form expression for it.

Number of extra calls required is also Fibonacci kind of sequence.

0 0 2 2 4 6 10 16 26 42 68 110 178 288 466

#include<iostream>
using namespace std;

int a = 0;
int b = 0;

int fib(int n) {
    a++;
  if(n == 0) return 0;
  if(n == 1) return 1;
  if(n == 2) return 1; //LINE 3 HERE <---

  return fib(n - 1) + fib(n - 2);
} 

int fib1(int n) {
    b++;
  if(n == 0) return 0;
  if(n == 1) return 1;

  return fib1(n - 1) + fib1(n - 2);
}

int main(int argc, char* argv[])
{
    for(int i =0 ;i<15;i++)
    {
        fib(i);
        fib1(i);

        cout<<b-a<<" ";

        b = a = 0;
    }
}

NOTE: I thought it would be some constant but...

Let's assume that there's no 3rd line and calculate f(3):

f(3) = f(2) + f(1)
f(1) = 1
f(2) = f(1) + f(0)
f(0) = 0
f(1) = 1

It takes 3 calls to calculate f(2) now. It there was a 3rd line then this will be done in 1 call.

The complexity of this algorithm (without 3rd line) is O(2^n). When you add line 3, which contain explicit solution for the case when n = 2 the complexity becomes O(2^(n-1)) what is equals to (1/2) * O(2^n) = kO(2^n) where koefficient k = 0.5. If you add explicit solution for the case where n = 3 then you get k = 0.25 and so on. When you add p explicit solutions the complexity will be:

    1
O (--- * 2^n)
   2^p 

This means that if you will calculate the answer for n from 1 to n and if you'll save all calculated solutions then you'll get p = n - 1 and the algorithm for each of n steps and the comlexity will be 2*O(n).