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