6,239 views
1 votes
1 votes

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()
 

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

Answer:

Related questions

1 votes
1 votes
2 answers
1
nbhatt asked Nov 3, 2022
372 views
Is ln(n!)=theta(n ln(n))?
0 votes
0 votes
1 answer
2
nbhatt asked Nov 3, 2022
276 views
If big oh is possible for an algorithm but big Omega is not,then is it small o?
1 votes
1 votes
1 answer
3
AIkiran01 asked Jul 14, 2018
1,876 views
which of the following estimates are true? Explain with valid reasons.a) (2n)! is theta (n)!b) log((2n)!) is theta (log(n)!)
0 votes
0 votes
1 answer
4