retagged by
502 views

2 Answers

Best answer
1 votes
1 votes
a) without DP

recurrence relation for #calls is T(n) =  T(n-1) + T(n-2) + 2    (becoz here 2 Distinct recursive calls T(n-1) and  T(n-2))

T(0) = 0

T(1) = 0

(here no recursive calls for T(0) and T(1))

T(2 )= T(1) + T(0) + 2 = 2

T(3 )= T(2) + T(1) + 2 = 4

T(4 )= T(3) + T(2) + 2 = 8

so total # calls including first call(T(4)) = 8+1=9

b) with DP

in DP we have to evaluate every function call exactly once.

so for fib(4) we have to evaluate fib(3),fib(2),fib(1) and fib(0),,,,,,,ie n+1 function call

so total 5 function call.
selected by
0 votes
0 votes
Suppose we're calculating fib(5) then there will be 6 unique function calls f(5), f(4), f(3), f(2), f(1), f(0), So i think there should be n+1 function calls in Dynamic Programming.

Btw, without mentioning the value of n, how can you generalize number of function calls?

Related questions

2 votes
2 votes
1 answer
1