+1 vote
105 views

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

| 105 views
+1

RR for fun1

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

RR for fun 2

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

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.

+2

@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

+1

thanks @Shubham Shukla

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

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

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

by Junior (905 points)

+1 vote