GATE CSE 2008 | Question: 74

Question

Consider the following C functions:

int f1 (int n)
{
    if(n == 0 || n == 1)
        return n;
    else
        return (2 * f1(n-1) + 3 * f1(n-2));
}
int f2(int n)
{
    int i;
    int X[N], Y[N], Z[N];
    X[0] = Y[0] = Z[0] = 0;
    X[1] = 1; Y[1] = 2; Z[1] = 3;
    for(i = 2; i <= n; i++){
        X[i] = Y[i-1] + Z[i-2];
        Y[i] = 2 * X[i];
        Z[i] = 3 * X[i];
    }
    return X[n];
}

The running time of $f1(n)$ and $f2(n)$ are

• A. $\Theta(n)$ and $\Theta(n)$
• B. $\Theta(2^n)$ and $\Theta(n)$
• C. $\Theta(n)$ and $\Theta(2^n)$
• D. $\Theta(2^n)$ and $\Theta(2^n)$

Comments

O(3^n)

---

the solution of the recurrence relation provided by you, T(n) = 2T(n-1) + 3T(n-2) , would contain a term having 3ⁿ but the it would be of  O(2ⁿ). (Check the comments by bhuv below arjun sir's answer)

---

This is a classic example of how dynamic programming reduces the timec complexity of an algorithm.

For a similar example, take the case of finding the nth Fibonacci number.

Using recursion, we'll write the code as:
 

int fib(int n)

{

    if (n <= 1)

        return n;

    return fib(n-1) + fib(n-2);

}

 

This will give an exponential time complexity.

However, we can use an array to find the result in amuch more efficient way:

 

   f[0] = 0;

  f[1] = 1;

  

  for (i = 2; i <= n; i++)

  {

      f[i] = f[i-1] + f[i-2];

  }

 

 

 

This will only take O(n) time.

Answer 1

The complexity is related to input-size, where each call produce a binary-tree of calls

Where T(n) make 2^n calls in total ..

T(n) = T(n-1) + T(n-2) + C

T(n) = O(2^n-1) + O(2^n-2) + O(1)

O(2 ^n)

In the same fashion, you can generalize your recursive function, as a Fibonacci number

T(n) = F(n) + ( C * 2n)

Next you can use a direct formula instead of recursive way

Using a complex method known as Binet's Formula

FORM STACK OVER FLOW.

Answer 2

(B.) In f1 function calling itself 2 times in recusive nature so O(2^n) and f2 is in normal form so it is O(n)