The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+21 votes

Consider the following C functions:

int f1 (int n)
    if(n == 0 || n == 1)
        return n;
        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.9k points)
edited by | 3.9k views

$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

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

clear 1 doubt please

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

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

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. 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 (386k points)
edited by

@Mk Utkarsh

Is it fine ?

I mean options are "theta ( )"

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

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

@Shaik Masthan 

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

exaggerate the same way ?

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

@Shaik Masthan 

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

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

@Shaik Masthan 

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

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

if yes, it is very tough :)

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

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)
any one can please suggest me how to count the complexity in this equation...i didnt get it...
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.

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
48,691 questions
52,776 answers
68,387 users