The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+25 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)$
in Algorithms by Veteran (52.1k points)
edited by | 4.5k 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

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

by Veteran (420k points)
edited by

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

@Ayush Upadhyaya

$\Omega \left ( 2^{n-1} \right )$ or $\Omega \left ( 2^{\frac{n}{2}}\right )?$


@Ayush Upadhyaya Why Theta is wrong?


@Arjun-Sir because  we have the following recurrence 


Recurrence tree


Cost at height 0-$2^0.c$

Cost at height 1-$2^1.c$

Cost at height h-$2^h.c$

Best case height $n-2k=0 \rightarrow k=\frac{n}{2}$

So, best case cost = $c \bigg \{2^0+2^1+....2^{\frac{n}{2}} \bigg \}=c.\frac{2^{\frac{n}{2}+1}-1}{2-1}=\Omega(2^{n/2})$

Saying $\theta(2^n)$ implying $\Omega(2^n)$ and $O(2^n)$, so that's why saying $\theta(2^n)$ for f1 would be incorrect.

@ayush sir can you please explain n=2k step.
+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.

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
50,309 questions
55,742 answers
90,452 users