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(n²)
- D. O(2^n)
Answer: D. O(2^n)
Explanation: T(n) = 2T(n-1) + C. This recurrence solves to O(2^n).