The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
3.7k 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];
}

The running time of $f1(n)$ and $f2(n)$ are

  1. $\Theta(n)$ and $\Theta(n)$
  2. $\Theta(2^n)$ and $\Theta(n)$
  3. $\Theta(n)$ and $\Theta(2^n)$
  4. $\Theta(2^n)$ and $\Theta(2^n)$
asked in Algorithms by Veteran (59.8k points)
edited by | 3.7k views
+2

$f1(n)$ will form approximate a complete binary tree and the cost of each node is constant, hence T.C of f1(n) will be
$\theta(2^n)$ 

In $f2(n)$ ignore everything except the for loop, the for will run (n-2) time hence, T.C is $\theta(n)$

Correct option is (B).

+1
clear 1 doubt please

i am having characteristic polynomial as r^2 - 2*r-3=0 with roots as 3 , -1?
0
and what are the base conditions?
0
f1(n) = c1.(r1)^n + c2.(r2)^n

base condition will only help to evaluate constants that will not change the answer (3^n)
0
and what is the correct answer according to you?
0
O(3^n)
0

the solution of the recurrence relation provided by you, T(n) = 2T(n-1) + 3T(n-2) , would contain a term having 3n but the it would be of  O(2n). (Check the comments by bhuv below arjun sir's answer)

2 Answers

+32 votes
Best answer

Q.$74$ = option B
Q.$75$ = option C

Time complexity of $f1$ is given by
$T(n) = T(n-1) + T(n-2)$, (multiplication by $2$ and $3$ won't affect complexity as it is a constant time operation)
$T(0) = T(1) = 1$

The solution to this (fibonacci series) is given by Golden ratio. https://en.wikipedia.org/wiki/Golden_ratio which is $O(2^n)$. (Using theta in question must be a mistake)

Time complexity of $f2$ is $\Theta(n)$ as here all recursive calls are avoided by saving the results in an array (dynamic programming). 

So, answer to $74$ is (B).

$75$. Both $f1$ and $f2$ are calculating the same function. So, 

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

answered by Veteran (379k points)
edited by
0

@Mk Utkarsh 

https://gateoverflow.in/495/gate2008-74?show=231375#c231375

Is it fine ?

I mean options are "theta ( )"

So instead of "exact" we go for upper bound, will it be fine ?

0
Actually, in the options, it should be $O(2^n) \;instead \;of\; \theta(2^n)$
0

@Shaik Masthan 

But if somewhere "theta" is the condition then can we

exaggerate the same way ?

+1
if there is no other option to you, then you can do it
0

@Shaik Masthan 

​​​​​​Traditional method is tedious , can you solve it by substitution ?

+2
T(n) = T(n-1)+T(n-2) + c ===> (i)

note that T(n-1) > T(n-2)

T(n-1) + T(n-2) < T(n-1) +T(n-1)  ===> (ii)

substitute (ii) in (i)

T(n) =  2.T(n-1) + c

T(n) = 2 (2.T(n-2) + c ) + c = 2$^2$ T(n-2) + 2$^1$c + 2$^0$c

after k iterations,

T(n) = 2$^k$ T(n-k) + 2$^{k-1}$c+..... + 2$^0$c = 2$^k$ T(n-k) + (2$^{k}-1)$c ----> (iii)

let n-k=1 ===> k=n-1 ---> (iv)

substitute (iv) in (iii), then it look like

T(n) = 2$^{n-1}$ T(1)  +  (2$^{n-1}-1)$c

===> T(n) = O( 2$^n$ )
0

@Shaik Masthan 

Thanx for the derivation but actually i was asking for that can we use substitution in its original homogeneous form.

0
did you mean, T(n) = T(n-1)+T(n-2) + c ?

if yes, it is very tough :)
0

@Shaik Masthan 

Okay. So tradiotradi way will be better then. But i guess they wont ask non homogeneous as its time consuming. 

Thanx for the help :)

0
for f1, can we say here that Time complexities are $O(2^n)$ and $\Omega(2^{n/2})$?

So, yes Using theta here is a mistake.
+4 votes

74. Answer is B

The f1(n) is a recursive function. The recurrence equation for f1(n) is

T(0) = 0

T(1) = 1

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

The solution of this equation contains a polynomial of 2n so on average the running time of f1(n) is \Theta(2n).

75. Answer is C.

f2(n) is the non-recursive version of f1(n) so the output of both the functions is same.

answered by Boss (19.9k points)
0
any one can please suggest me how to count the complexity in this equation...i didnt get it...
0
May you plz explain how yu are getting O(2^n) in the solution of this polymomial??coz m.getting O(3^n) solving it.i am.using the equation x^2-2x-3=0

Plz explain.
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

47,241 questions
51,468 answers
178,538 comments
66,754 users