+22 votes
2k 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$

edited | 2k views
0

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

## 5 Answers

+12 votes
Best answer

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

by Boss (12.2k points)
selected by
0
Sir how did you find the characteristic equation
+1

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

+17 votes

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

$f1(8)$

$f2(8)$ will return 1640

by Boss (38.7k points)
edited
+3
Both the programs are virtually the same, one is using recursion and one is not. In exam we can directly deduce and solve faster if we are confident enough I guess ?
0
@ravi

how u know they are equal  ?
0

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

+6 votes

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

by Boss (17.8k points)
edited
0
Any faster way to solve this question?
+5 votes
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.
by Active (1.5k points)
+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.
by Boss (13.8k points)
edited by
0
@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:

+26 votes
2 answers
1
+24 votes
6 answers
2
+50 votes
6 answers
3
+17 votes
3 answers
4