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

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.

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! – Pratik Deoghare Mar 13 '10 at 11:32 TN is "Time of New code", TO is "Time of Old code" – jpalecek Mar 13 '10 at 11:38 1 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 Mar 13 '10 at 11:38 1 @TheMachineCharmer: “Where did you learn this? € – this is directly from the curriculum of introductory computer science. So it’s literally CS 101.

;-) – Konrad Rudolph Mar 13 '10 at 11:39 Wow this is actually a good analysis. And I think the same way of reasoning can be applied to other recursive algorithms also. – BROCK Mar 13 '10 at 12:37.

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 using namespace std; int a = 0; int be = 0; int fib(int n) { a++; if(n == 0) return 0; if(n == 1) return 1; if(n == 2) return 1; //LINE 3 HERE.

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

Sorry, but this is totally inaccurate – jpalecek Mar 13 '10 at 11:14.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.