The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+10 votes

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);
    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)$?
asked in Programming by Veteran (69k points)
edited by | 603 views

2 Answers

+20 votes
Best answer

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 (347k points)
edited by
dont you think it should be f(n) instead of f(n-2) in the above code ?
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.
sir , i could not get question  :(
We are using dynamic programming to reduce the time complexity of recursive solution to Fibonacci.
o yeah... i could not think in this way...

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

thank you :)

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

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

@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 vote

int fib(int n)


  if (n>m)



       return 1;


      return 1;

  if (f[n]!=0)

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


  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 (35 points)
edited by

this code we are testiong on matlab

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

for i=1:100



Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,170 questions
40,846 answers
39,703 users