The Fibonacci function is dened as follows: F(0) = 1 F(1) = 1 F(n) = F(n1) + F(n

Question

The Fibonacci function is dened as follows:

F(0) = 1

F(1) = 1

F(n) = F(n1) + F(n2) for n > 2

1. Assume you implement a recursive procedure for computing the Fibonacci sequence based directly on the function dened above. Then the running time of this algorithm can be expressed as: T(n) = T(n1) + T(n2) + 1 Choose from the following asymptotic bounds the one that best satises the above recurrence and explain your selection:

i T(n) = O(n)

ii T(n) = O(n2)

iii T(n) = (cn), for some constant c

iv T(n) = (nn)

2. What specically is wrong with your algorithm? (i.e., what observation can you make to radically improve its running time?)

3. Give a memoized recursive algorithm for computing F(n) eciently. Write the recurrence for your algorithm and give its asymptotic upper bound.

Explanation / Answer

1.
Ans: iii T(n) = (cn), for some constant c

2.
Time Complexity: T(n) = T(n-1) + T(n-2) which is exponential.
We can observe that this implementation does a lot of repeated work (see the following recursion tree). So this is a bad implementation for nth Fibonacci number.

                         fib(5)
                     /                
               fib(4)                fib(3)
             /                      /     
         fib(3)      fib(2)         fib(2)    fib(1)
        /              /            /    
fib(2)   fib(1) fib(1) fib(0) fib(1) fib(0)
/   
fib(1) fib(0)

Extra Space: O(n) if we consider the function call stack size, otherwise O(1).

3)

int fib(int n)
{
/* Declare an array to store Fibonacci numbers. */
int f[n+1];
int i;

/* 0th and 1st number of the series are 0 and 1*/
f[0] = 0;
f[1] = 1;

for (i = 2; i <= n; i++)
{
      /* Add the previous 2 numbers in the series
         and store it */
      f[i] = f[i-1] + f[i-2];
}

return f[n];
}

Time Complexity: O(n)
Extra Space: O(n)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.