7,230 views

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$

### 1 comment

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

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)$

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. :)

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

$f1(8)$

$f2(8)$ will return 1640

by

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.

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).

Any faster way to solve this question?

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.

correct👍

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

by