The time complexity of the following C function is (assume n > 0) int…
2015
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));
}
- A.
O(n)
- B.
O(n log n)
- C.
O(n2)
- D.
O(2n)
Attempted by 116 students.
Show answer & explanation
Correct answer: D
To determine the time complexity, analyze the recursive calls. For any input n > 1, the function executes two recursive calls: recursive(n-1) + recursive(n-1). This establishes the recurrence relation T(n) = 2T(n-1). Since the recursion depth is n and the number of calls doubles at each level, the total operations grow exponentially. Therefore, the asymptotic time complexity is O(2^n).