in Algorithms
6,199 views
1 vote
1 vote

Consider the following two functions. What are time complexities of the functions?

int fun1(int n)

{

    if (n <= 1) return n;

    return 2*fun1(n-1);

}

int fun2(int n)

{

    if (n <= 1) return n;

    return fun2(n-1) + fun2(n-1);

}

 

(A) O(2^n) for both fun1() and fun2()
(B) O(n) for fun1() and O(2^n) for fun2()
(C) O(2^n) for fun1() and O(n) for fun2()
(D) O(n) for both fun1() and fun2()
 

in Algorithms
6.2k views

4 Comments

Answer is option B.

RR for fun1

T(n) = T(n-1) +1

RR for fun 2

T(n) = 2× T(n-1) +1
1
1

what i am not getting is that In fun1() return 2*fun(n-1); can be written as return fun(n-1) + fun(n-1);

then T(n)=2*T(n-1)+1 for fun1 also.

0
0

@rishav

thats wrong interpretation

fun(n-1) is only called once not twice ,the constant 2 is multiplied to this function call, if you need to analyse you just need to just see how many recursive function calls there,here its 1 only

 

return 2*fun(n-1)

you can rewrite above statement as:

y=fun(n-1)

z=2*y

return z

2
2

thanks @Shubham Shukla

 

1
1

1 Answer

0 votes
0 votes

BIG NOTE: 2*f(n-1)  is not equal to f(n-1)+f(n-1) because there are only one recursive call in 2*f(n-1) while there are two recursive call in f(n-1)+ f(n-1).

1. Recurrence relation for T(n) = T(n-1) + C

Solution for first code

2. T(n) = 2T(n-1) + C 

This will be O($2^{n}$ )