MCQ PracticeSingle Best AnswerTopic: Dynamic Programming
Q
What is the space complexity of the dynamic programming algorithm for computing the nth Fibonacci number using memoization?
Question ID
#5721
Subchapter
Dynamic Programming
Action
Choose one option below
Choose Your Answer
Click an option to check whether your answer is correct.
A
O(1) ✔✖
B
O(log n) ✔✖
C
O(n) ✔✖
D
O(n^2) ✔✖
C
Correct Answer: C
Explanation
Answer: O(n)
Explanation: The dynamic programming algorithm for computing the nth Fibonacci number using memoization has a space complexity of O(n) because it involves storing the solutions to n subproblems in memory.