in Algorithms edited by
7,223 views
29 votes
29 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$
in Algorithms edited by
7.2k views

1 comment

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

0
0

5 Answers

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

selected by

2 Comments

Sir how did you find the characteristic equation
0
0

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

12
12
21 votes
21 votes

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

$f1(8)$

 

 

$f2(8)$ will return 1640

 

edited by

4 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

0
0
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!!?
0
0
@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.
0
0
13 votes
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).

edited by

4 Comments

Any faster way to solve this question?
0
0

practice!

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

correct👍

0
0
6 votes
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.
by
Answer:

Related questions