1k views

A recursive program to compute Fibonacci numbers is shown below. Assume you are also given an array $f [ 0......m]$ with all elements initialized to $0$

fib(n) {
if (n > M) error ();
if (n == 0) return 1;
if (n == 1)return 1;
if (▭)________________________(1)
return ▭__________________(2)
t = fib(n - 1) + fib(n - 2);
▭_____________________________(3)
return t;
}

1. Fill in the boxes with expressions/statement to make $fib()$ store and reuse computed Fibonacci values. Write the box number and the corresponding contents in your answer book.
2. What is the time complexity of the resulting program when computing $fib(n)$?
edited | 1k views

Array $f$ is used to store the $fib()$ values calculated in order to save repeated calls. Since $n = 0$ and $n = 1$ are special cases we can store $fib(2)$ to $f[0], fib(3)$ to $f[1]$ and so on. The missing code completed would be:

if (f[n - 2] != 0){
return f[n-2];
}
t = fib(n-1) + fib(n-2);
f[n-2] = t;
return t;

In this code, $fib(i)$ will do a recursion only once as once $fib(i)$ is calculated it is stored in array. So, the time complexity for $fib(n)$ would be $\Theta(n)$.

PS: We can also store $fib(n)$ in $f(n)$, the above code just saves $2$ elements' space in the array.

answered by Veteran (406k points)
edited by
0
dont you think it should be f(n) instead of f(n-2) in the above code ?
+2
depends on how we store in array f[]. I already mentioned that fib[i] will be stored at f[i-2] as we don't store fib(0) and fib(1) in array- their checks are done at the beginning of the given code, so no point in storing them in array.
+1
thanx
0
sir , i could not get question  :(
+2
We are using dynamic programming to reduce the time complexity of recursive solution to Fibonacci.
+1
o yeah... i could not think in this way...

values store in table and  then reuse ... got it !

thank you :)
+1

That we say as Memoized Version in Dynamic Programming. Am I correct Arjun Sir??

0
@Abbas rt...
0
@papesh
What is Memoized Version in Dynamic Programming. how it differ from dynamic programming?
0
if f(n-2) is 0 that condition is not given

rt?
0
@Arjun sir,

Lets us say i calculated f(3) and f(2) and store in table.

Now f(4) is called,it needs f(3) and f(2), it will look into table for f(4) but will not find that.So,it will again call f(3) and f(2),which are already calculated(although that calls to  f(3) and f(2) will return in constant time ,but does this effect time complexity?
+1
0
Thank you
+1

Below is a snapshot of how this works

Consider my f[] array is as below

What this code does is, it does not store value for fib(0) and fib(1), rather it stores values of fib(n) for $n \geq2$

in f[n-2].

So, for Fib(2), the value is stored in f[0], for Fib(3), the value is stored in f[1] and so so...

Consider I have invoked Fib(10)

Below is the execution sequence

Now, it looks like the time complexity for this program will be $2^n$, but it's not.

When, the recursion will bottom out and start to trace back, it will use the values from the table for the repeated function calls involved.

Like at last, for Fib(2), it calls Fib(1)+Fib(0) and it gets resolved without further recursion and value returned is 2 and it is stored in f[0].

Now, when recursion goes back

for fib(3)=fib(2)(return value 2)+fib(1)(gives 1)=3 and stored in f[1]=3 and 3 returned to the caller fib(4).

Then  we go back

fib(4)=fib(3)(return value 3)+fib(2) (Now this fib(2) will use value from the table f[2-2]=f[0]=2)=3+2=5 stored in f[4-2]=f[2]=5.

And it goes on untill it finally evaluated fib(10).

So, number of function calls made for fib(10)=19

So, for fib(n) number of function calls would be $2n-1$

So, time complexity $\theta(n)$

int fib(int n)

{

if (n>m)

printf('error');

if(n==0)

return 1;

if(n==1)

return 1;

if (f[n]!=0)

return (f[n-1]+f[n-2]);\\\ this is for reuse

t=fib(n-1)+fib(n-2);

f[n]=t ; \\ this for store the value

return t;

}

In Array f[0...m] store all the value of  Fibonacci numbers 0 to m

time complexity is O(n)

answered by (55 points)
edited by
0

for run upper code we use another function as main() shown in below

f=zeros(1,100);
for i=1:100
f(i)=fib(i,f);
end

input_f

output_f

1
2
+1 vote