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

Dark Mode

7,666 views

30 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

- $1661$ and $1640$
- $59$ and $59$
- $1640$ and $1640$
- $1640$ and $1661$

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

21 votes

0

0

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

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.

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.

0

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

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.