Question

The time complexity to compute the 15\(^\text{th}\) Fibonacci number using dynamic programming is _______ .

• A. O(1)
• B. O(n)
• C. O(n\log n)
• D. O(\(\log n\))

Hint:

Dynamic programming significantly improves the time complexity of recursive problems like the Fibonacci sequence by avoiding redundant computations.

Answer 1

The Correct Option is B

When using dynamic programming to compute the Fibonacci number, we store intermediate results to avoid redundant calculations. This results in a linear time complexity of \(O(n)\). Using memoization or tabulation techniques, we can compute the Fibonacci number in linear time, making it much faster than the recursive approach.