What is the time complexity of the following C function? (Assume n > 0) int…
2025
What is the time complexity of the following C function? (Assume n > 0)
int rec (int n)
{
if (n == 1)
return 1;
else
return (rec (n - 1) + rec (n - 1));
}
Answer: B. O(2n) — The function rec(n) calls itself twice with input n-1, creating a recurrence relation T(n) = 2T(n-1). The recursion tree depth is n, and the number of nodes…
- A.
O(n2)
- B.
O(2n)
- C.
O(n log n)
- D.
O(n)
Attempted by 196 students.
Show answer & explanation
Correct answer: B
The function rec(n) calls itself twice with input n-1, creating a recurrence relation T(n) = 2T(n-1). The recursion tree depth is n, and the number of nodes grows exponentially at each level. This results in a time complexity of O(2^n).
Loading lesson…