Time complexity of program

Question

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));
}

I have to find the running time of f1(n)

My Solution:-

The recurrence relation for running time of f1(n) can be written as

T(n) = T(n-1) + T(n-2) + c
Where c is a constant
Also T(0) =  T(1) = O(1) {Order of 1 (Constant Time)}

Then I used recursion tree method for solving this recurrence relation

            ---
             |                   n  -------------------- cost = c     
             |                /     \
             |              n-1      n-2 ---------------- cost = 2c
             |             /  \      /   \
             |           n-2  n-3   n-3  n-4 ------------ cost = 4c
(n-1) levels |           /                 \
             |         ......................
             |        ........................
             |       .........................\
             |      ..........................n-2k
             |      /
            ---    n-k

The left sub tree goes till

n-k = 1 => k = n-1

So the asymptotic upper bound comes out to be

c+2c+2^2c+2^3c+....+2^(n-1)c
    = Big-Oh(2^n)

Similarly the right sub tree goes till

n-2k = 1 => k = (n-1)/2

So the asymptotic lower bound comes out to be

c+2c+2^2c+2^3c+....+2^((n-1)/2)c
   = Big-Omega(2^(n/2))

Since the upper and the lower bounds differ by a function (and not by a constant value)

Upper bound = 2^n =  2^(n/2) * 2^(n/2)
Lower bound = 2^(n/2)

so in my opinion I cannot write T(n) = Theta(2^n)

But the answer to this question is given as time complexity = Theta(2^n)

What am I doing wrong?

Since theta is the upper bound, why does it matter how it differs from the lower bound? — Richard, Jun 13 '17 at 18:20
Actually Theta is both in O and Omega, i.e., it is upper and lower bound. — gue, Jun 13 '17 at 18:32

score 2 · Accepted Answer · answered Jun 13 '17 at 18:52

The recurrence is equivalent to the fibonacci numbers, there is a lot information about this recurrence on wikipedia. It is true that fibonacci is in O(2^n) and in Omega(2^(n/2)). There are related questions that mention this bounds as well as a tight bound of ~θ(1.6n).

score 0 · Answer 2 · answered Jun 13 '17 at 18:55

0

Only the last level is calculated. Other layer is just calling the next layer.

answered Jun 13 '17 at 18:55

Zeta

913
10
24

Time complexity of program

2 Answers2