The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
2.1k 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 (68.9k points)
edited by | 2.1k 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
$\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).

2 Answers

+28 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 (332k points)
edited by
@arjun sir,

how can we ignore the constants 2 and 3 ?

the nature of subtract and conquer theorem is T(n)=aTt(n-b)+f(n)....so can we ignore constant 'a' here ?
Very good explanation.

$return ( f(n-1) + f(n-1) + f(n-2) +f(n-2)+f(n-2)) \neq return( 2*f(n-1) + 3*f(n-2))$

If it was 
  return ( f(n-1) + f(n-1) + f(n-2) +f(n-2)+f(n-2))
then while calculating time complexity we will take f(n)= 2f(n-1) + 3f(n-2)
because there are two f(n-1) operation and 3 f(n-2) which give there contribution in time complexity as each will execute separately whe they were called.
Also note that its Recurrence relation for VALUE also will be f(n)= 2f(n-1) + 3f(n-2).

NOW SEE THE CHANGE

---------------------------------------------------------------------------------------
But for return( 2*f(n-1) + 3*f(n-2)) multiplying by 2 and 3 are just constant time operations,
so recurrence relation for T.C. will be f(n)=f(n-1)+f(n-2).
but if you calculate Recurrence relation for VALUE it will be
f(n) = 2 * f(n-1) + 3 * f(n-2), as value will be get effected by multiplication.

@bhuv

your point is correct. But don't you think we will get same upper bound of time in both cases that you mentioned?

No,

return ( f(n-1) + f(n-1) + f(n-2) +f(n-2)+f(n-2)) 
then while calculating time complexity we will take f(n)= 2f(n-1) + 3f(n-2) 

T.C. =O(3n)

return( 2*f(n-1) + 3*f(n-2)) multiplying by 2 and 3 are just constant time operations, 
so recurrence relation for T.C. will be f(n)=f(n-1)+f(n-2). 

T.C. = O(2n)

You can solve both equations by the method of Linear Homogeneous Recurrence relation with constant coefficients.

 

@bhuv

f(n)=2*f(n-1) + 3*f(n-2)

let g(n)=5*g(n-1)

Solving g(n) T.C= O(5n)

now f(n)<=g(n)

so can't we say that upper bound for f(n)=O(5n).?

I thought your were talking more precisely "what is upper bound on T.C. of both of those separately ?"

Yes, both O(2n) and O(3n) can be written as O(5n), even O(nn), you can grow above as much you want, you can write these type of upper bound while solving simpler or solo Time complexity comparisons question like which one is O of which one.
But I think that is not a good practice to do while giving an answer to RRs or TC of given algorithms because there upper bound generally means "time taken by an Algorithm in worst case scenario".

 

I think this might be helpful: LINK.

 

What I meant was O(5n) be the tightest upper bound?

Anyways how you got 3n?

+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 Veteran (19.6k 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.


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

32,694 questions
39,293 answers
110,109 comments
36,701 users