Question

What does the following function compute? Give an analysis of its complexity

int fun1 (int n)

{

if (n == 0)

    return 1;

else

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

}

Answer 1

for an input of n, this function calculates the returns the value of 2 raised to the power of n.
fun1(n) = 2^n

this is a recursive function
recurrence relation of this function is T(n) = 2T(n-1) + O(1)

solving the recurrence relation:
----------------------------------
T(n)
= 2T(n-1) + 1
= 2(2T(n-2) + 1) + 1
= 2(2(2T(n-3) + 1) + 1) + 1
= 2^3T(n-3) + 2^2 + 2^1 + 1
= 2^nT(1) + 2^n-1 + ... + 1
= 2^n + 2^n-1 + ... + 1
= 2^(n+1) - 1
so, T(n) = O(2^n)

Time complexity: O(2^n)