Register

GATE CSE 2008 | Question: 75

• edited by
12,695 views
33 votes
33 votes

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];
}

$f1(8)$ and $f2(8)$ return the values

  1. $1661$ and $1640$
  2. $59$ and $59$
  3. $1640$ and $1640$
  4. $1640$ and $1661$
• edited by
User Avatar

5 Answers

2 votes
2 votes
f1 and f2 are computing same function. f1 is Top Down  method using recursion and f2 is  Bottom Up method using DP.

This problem could be solved via forming recurrence relation. Solution of Homogenous recurrence relation is ->

a(n) = $\frac{1}{4}*(3^n - (-1)^n)$

a(8) = 1640.

Hence answer is C part.
• edited by
User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

41 votes
41 votes
7 answers
2
Kathleen asked Sep 12, 2014
21,711 views
GATE CSE 2008 | Question: 47
We have a binary heap on $n$ elements and wish to insert $n$ more elements (not necessarily one after another) into this heap. The total time required for this is $\Theta(\log n)$ $\Theta(n)$ $\Theta(n\log n)$ $\Theta(n^2)$
We have a binary heap on $n$ elements and wish to insert $n$ more elements (not necessarily one after another) into this heap. The total time required for this is$\Theta(...
User Avatar
79 votes
79 votes
7 answers
3
Kathleen asked Sep 12, 2014
36,629 views
GATE CSE 2008 | Question: 40
The minimum number of comparisons required to determine if an integer appears more than $\frac{n}{2}$ times in a sorted array of $n$ integers is $\Theta(n)$ $\Theta(\log n)$ $\Theta(\log^*n)$ $\Theta(1)$
The minimum number of comparisons required to determine if an integer appears more than $\frac{n}{2}$ times in a sorted array of $n$ integers is$\Theta(n)$$\Theta(\log n)...
User Avatar
28 votes
28 votes
6 answers
4
Kathleen asked Sep 11, 2014
13,426 views
GATE CSE 2008 | Question: 7
The most efficient algorithm for finding the number of connected components in an undirected graph on $n$ vertices and $m$ edges has time complexity $\Theta(n)$ $\Theta(m)$ $\Theta(m+n)$ $\Theta(mn)$
The most efficient algorithm for finding the number of connected components in an undirected graph on $n$ vertices and $m$ edges has time complexity$\Theta(n)$$\Theta(m)$...
User Avatar
Link Copied!