views:

165

answers:

3

I just got this question 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);
}
A: 

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

Roman
Sorry, but this is totally inaccurate
jpalecek
+4  A: 

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

TheMachineCharmer
So, the answer can be expressed as ... `2 * fib(n-2)` ? :)
Hamish Grubijan
+6  A: 

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.

jpalecek
+1 Awesome. Where did you learn this?? I mean I want to learn to analyze programs in this way!! What is TN and TO??? You are a genius. This is your answer @BROCK!! ACCEPT IT!!
TheMachineCharmer
TN is "Time of New code", TO is "Time of Old code"
jpalecek
You could have mentioned that the closed form (like the closed form of the original Fibonacci sequence) is an exponential expression, hence the additional complexity of removing line 3 is exponential in *n*. Still, very good analysis, this is how it should be done.
Konrad Rudolph
@TheMachineCharmer: “Where did you learn this?” – this is directly from the curriculum of introductory computer science. So it’s **literally** CS 101. ;-)
Konrad Rudolph
Wow this is actually a good analysis. And I think the same way of reasoning can be applied to other recursive algorithms also.
BROCK