GATE CSE 2008 | Question: 75

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

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

• A. $1661$ and $1640$
• B. $59$ and $59$
• C. $1640$ and $1640$
• D. $1640$ and $1661$

Comments

Question regarding the running times of f1(n) and f2(n) : https://gateoverflow.in/495/gate2008-74

---

Smart way to answer:(Exam approach)

By analyzing f1 and f2 we are sure that both codes are same so answer of f1=f2( option A and D gon)

By running couple of steps we are sure that answer will be a big number so (option B gon)

C is correct answer

Answer 1

Both $f1$ and $f2$ are calculating the same function in recursive and iterative fashion respectively.

So. lets solve the recurrence relation.

$F(n) = 2 F(n-1) + 3F(n-2)$

Its characteristic equation will be
$r^{2}- 2r- 3 = 0$
$\implies (r-3) (r+1) = 0$
$\implies r = 3, -1$

Now, we have two roots. So the equation will be

$a_{n} = C_{1}(-1^{n}) + C_{2}(3^{n}) \qquad \to (1)$

Now from the function  $f1,$

$F(0) = 0$ and  $F(1) = 1$

So, $C_{1} + C_{2} = 0$
$\quad -C_{1} + 3C_{2} = 1$

$\implies C_{1} = -1/4$  and  $C_{2} = 1/4$

After putting the values in $(i)$ the equation will become

$a_{n} = (-1/4)(-1^{n}) +(1/4)(3^{n})$

Putting $n= 8$ it will become  

$F(8) = a_{8} = 1640.$

---

Or we can do it manually

$f1(2) = 2f1(1) + 3f1(0) = 2$
$f1(3) = 2f1(2) + 3f1(1) = 7$
$f1(4) = 20$
$f1(5) = 61$
$f1(6) = 182$
$f1(7) = 547$
$f1(8) = 1640 = f2(8)$

Comments

Sir how did you find the characteristic equation

---

@Krishan-er

F(n) = 2 F(n-1) + 3 F(n-2)

Put F(n) = r$^{n}$, then F(n-1)=r$^{n-1}$ and also F(n-2)=r$^{n-2}$

Now the equation becomes,

r$^{n}$ = 2r$^{n-1}$ + 3r$^{n-2}$

Dividing the whole equation by r$^{n-2}$ we get

r$^{2}$ = 2r+3

r$^{2}$ - 2r - 3 = 0

And then the solution follows.

Hope this helps. :)

---

i know this is not a proper doubt but still actually we know f1 is 2^n and f2 is n^2 so how both can they both have equal values?

---

this value doesnt define the what will be the final answer they are just telling you how much the algorithm takes to get completed . think like this two person m1 and m2 does the same work but m1 take 10 days and m2 take 2 days so here the time taken vary but the work done is same . so this apply to f1 and f2

Answer 2

Here, answer is C. $1640$ and $1640$

$f1(8)$

 

 

$f2(8)$ will return 1640

 

Comments

yes replacing these three lines

 X[i] = Y[i-1] + Z[i-2];
        Y[i] = 2 * X[i];
        Z[i] = 3 * X[i];

we can get  this line

return (2 * f1(n-1) + 3 * f1(n-2))

So, both program working same

---

I have a doubt,

in f2 we are passing 8 as parameter therfore n=8

that means, int x[8] so the number of elements in x should be just 8 right!?

that means x[8] is not possible bcoz of 0 indexing!!?

---

@Manojk How is it possible that when n = 8 is passed and you have created and an array of 9 element each for X,Y,Z.

Answer 3

First, we'll see what $f1(8)$ will return

int f1(int n)

{

if(n == 0 || n == 1)

return n;

else

return(2*f1(n-1) + 3 * f1(n-2));

}

 

∴ $f1(8)$ returns $1640$

Now, what $f2(8) $ will return --

int i;

We can take any values of $i$, but at the end, we want the return value as $X[n]$, so we'll going to take $i=8$

int X[N], Y[N], Z[N];

The above line creates $3$ arrays 

X[0] = Y[0] = Z[0] = 0;

This will set all the index $0$ position of all the $3$ arrays to $0$

 

X[1] = 1; Y[1] = 2; Z[1] = 3;

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

This loop will run from $i=2$ to $i=8$

X[i] = Y[i-1] + Z[i-2];
Y[i] = 2 * X[i];
Z[i] = 3 * X[i];

when $i = 2$ ,

$X[ i ] = Y[ i-1 ] + Z[ i-2 ]$ $\rightarrow X[2] = Y[2-1] + Z[2-2] \\ = Y[1] + Z[0] = 2 + 0 \\ = 2$

$Y[i] = 2 * X[i]$ $\rightarrow Y[2] = 2 * X[2] \\ = 2 * 2 \\ = 4$

$Z[i] = 3 * X[i]$ $\rightarrow Z[2] = 3 * X[2] \\ = 3 * 2 \\ = 6$

when $i = 3$ ,

$X[ i ] = Y[ i-1 ] + Z[ i-2 ]$ $\rightarrow X[3] = Y[3-1] + Z[3-2] \\ = Y[2] + Z[1] = 4 + 3 \\ = 7$

$Y[i] = 2 * X[i]$ $\rightarrow Y[3] = 2 * X[3] \\ = 2 * 7 \\ = 14$

$Z[i] = 3 * X[i]$ $\rightarrow Z[3] = 3 * X[3] \\ = 3 * 7 \\ = 21$

when $i = 4$ ,

$X[ i ] = Y[ i-1 ] + Z[ i-2 ]$ $\rightarrow X[4] = Y[4-1] + Z[4-2] \\ = Y[3] + Z[2] = 14 + 6 \\ = 20$

$Y[i] = 2 * X[i]$ $\rightarrow Y[4] = 2 * X[4] \\ = 2 * 20 \\ = 40$

$Z[i] = 3 * X[i]$ $\rightarrow Z[4] = 3 * X[4] \\ = 3 * 20 \\ = 60$

when $i = 5$ ,

$X[ i ] = Y[ i-1 ] + Z[ i-2 ]$ $\rightarrow X[5] = Y[5-1] + Z[5-2] \\ = Y[4] + Z[3] = 40 + 21 \\ = 61$

$Y[i] = 2 * X[i]$ $\rightarrow Y[5] = 2 * X[5] \\ = 2 * 61 \\ = 122$

$Z[i] = 3 * X[i]$ $\rightarrow Z[5] = 3 * X[5] \\ = 3 * 61 \\ = 183$

when $i = 6$ ,

$X[ i ] = Y[ i-1 ] + Z[ i-2 ]$ $\rightarrow X[6] = Y[6-1] + Z[6-2] \\ = Y[5] + Z[4] = 122 + 60 \\ =182$

$Y[i] = 2 * X[i]$ $\rightarrow Y[6] = 2 * X[6] \\ = 2 * 182 \\ = 364$

$Z[i] = 3 * X[i]$ $\rightarrow Z[6] = 3 * X[6] \\ = 3 * 182 \\ = 546$

when $i = 7$ ,

$X[ i ] = Y[ i-1 ] + Z[ i-2 ]$ $\rightarrow X[7] = Y[7-1] + Z[7-2] \\ = Y[6] + Z[5] = 364 + 183 \\ = 547$

$Y[i] = 2 * X[i]$ $\rightarrow Y[7] = 2 * X[7] \\ = 2 * 547 \\ = 1094$

$Z[i] = 3 * X[i]$ $\rightarrow Z[7] = 3 * X[7] \\ = 3 * 547 \\ = 1641$

when $i = 8$ ,

$X[ i ] = Y[ i-1 ] + Z[ i-2 ]$ $\rightarrow X[8] = Y[8-1] + Z[8-2] \\ = Y[7] + Z[6] = 1094 + 546 \\ = 1640$

$Y[i] = 2 * X[i]$ $\rightarrow Y[8] = 2 * X[8] \\ = 2 * 1640 \\ = 3280$

$Z[i] = 3 * X[i]$ $\rightarrow Z[8] = 3 * X[8] \\ = 3 * 1640 \\ = 4920$

Now we'll be coming out from for loop & execute the last statement

return X[n];

which will return $X[n]$ i.e. $X[8]$ which is $1640$

∴ $f1(8)$ will return $1640$ & $f2(8)$ will also return $1640$

The correct option will be C).

Comments

Any faster way to solve this question?

---

Golam Murtuza

practice!

---

Both functions f1 and f2 are doing same thing (f1 is doing by recursion and f2 is doing by iteration). therefore we can say that

f1(8) = f2(8) by this we can eliminate option (a) and (d).

Now we have two choices option (b) and ( c ) one of them is correct-

f1(2) = 2f1(1) + 3f1(0) = 2;             f1(3) = 2f1(2) + 3f1(1) =7;

f1(4) = 2f1(3) + 3f1(2) = 20;            f1(5) = 2f1(4) + 3f1(3) = 61;

Here if f1(5) itself 61 then f1(8) should be greater than 61 therefore we can eliminate option (b) and so remaining

option ( c )  would be the answer.

---

Shreya2002

correct👍

Answer 4

Both functions are same. One is the recursive version and other is the itrative version. so find anyones's value is sufficient.

let's find value of f1(8).

f1(0)=0

f1(1)=1

f1(2)=2*f1(1) + 3*f1(0) = 2;   likewise for others

f1(3)=4 + 3 = 7

f1(4)=14 + 6 = 20

f1(5)=40 + 21 = 61

f1(6)=122 + 60 = 182

f1(7)=364 + 183 = 547

f1(8)= 1094 + 546 = 1640

(C.) is the answer.

Answer 5

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.

Comments

@Chhotu Boss

a(n) = (1/4)(3^n - (-1)^n).

do you mind if you please explain a bit about it and i mean upto very detail if you please.

Thanks anyway for your ans.

Answer 6

Smart way to answer:(Exam approach)

By analyzing f1 and f2 we are sure that both codes are same so answer of f1=f2( option A and D gon)

By running couple of steps we are sure that answer will be a big number so (option B gon)

C is correct answer 😊