edited by
18,709 views
40 votes
40 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];
}

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

6 Answers

Best answer
54 votes
54 votes

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 is (B).

edited by
5 votes
5 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.

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

T(n) <= 5T(n-1). { replaced 3T(n-2) by 3T(n-1)) therefore came this inequality

$T(n) = O(2^{n})$ using recursion tree method

 

Second one is clearly O(n) as a single for loop upto n is there.

So OPTION B is the right answer.
0 votes
0 votes

The correct answer is B.

The function f1 is similar to generating fibonacci sequence using recursion. Fibonacci sequence program have statement f(n-1) + f(n-2) instead of 2*f(n-1) + 3*f(n-2). Fibonacci sequence has exponential growth. Therefore, running time of f1 is $\Theta (2^n)$.

The function f2 runs for n-1 times. Hence running time for f2 is $\Theta (n)$.

Answer:

Related questions

41 votes
41 votes
7 answers
2
Kathleen asked Sep 12, 2014
21,515 views
We have a binary heap on $n$ elements and wish to insert $n$ more elements (not necessarily one after another) into this heap. The total time required for this is$\Theta(...
79 votes
79 votes
7 answers
3
Kathleen asked Sep 12, 2014
36,307 views
The minimum number of comparisons required to determine if an integer appears more than $\frac{n}{2}$ times in a sorted array of $n$ integers is$\Theta(n)$$\Theta(\log n)...
28 votes
28 votes
6 answers
4
Kathleen asked Sep 11, 2014
13,237 views
The most efficient algorithm for finding the number of connected components in an undirected graph on $n$ vertices and $m$ edges has time complexity$\Theta(n)$$\Theta(m)$...