Quiz Question 1 of 5
In the recursive implementation of the Fibonacci sequence, how does the time complexity of the algorithm change as n increases, and why?
Choose the correct answer below:
-
A
The time complexity is O(n!) due to the factorial nature of recursion in this problem.
-
B
The time complexity is O(2^n) because each Fibonacci number requires the sum of two recursive calls, leading to exponential growth.
-
C
The time complexity is O(n) because each function call only depends on the previous result.
-
D
The time complexity is O(log n) due to the binary nature of the recursion.