Time Complexity of Recursive Fibonacci
What is the time complexity of the following recursive fib method?
public static int fib(int n) {
if(n <= 1) return n;
return fib(n-1) + fib(n-2);
}
A
Exponential time, approximately O(2^n).
B
Logarithmic time, O(log n).
C
Quadratic time, O(n^2).
D
Linear time, O(n).
Question Leaderboard
Not enough data yet to show leaderboard.