PA of Algorithms Q40

0. The time complexity of the following C function is (assume n > 0)

int recursive (int n)
{
if (n = = 1)
return (1);
else
return(recursive(n-1)+ recursive(n-1));
}

Answer
Comment
Array

Option : D
Explanation :
Recurrence relation for function is
T (n) = 2 T (n – 1) + 1
= 2 [2T (n–2) + 1] + 1
= 4 T (n–2) + 2 + 1
= 4 [2T (n–3)+1] + 2 + 1
= 2³T (n–3) + 2² + 2 + 1
2k T (n–k) + 2^k-1 + ---2+1
put n–k = 1
So 2^n-1 T (1) + 2^n-2 + ----- 2 + 1
⇒ 2^n-1 + 2^n-2 + --- 2 + 1
⇒ 2^n-1 ⇒ O (2ⁿ).

Forgot your password?

I agree with the Terms.