Question

When a top-down approach of dynamic programming is applied to a problem, it usually _____________

(a) Decreases both, the time complexity and the space complexity

(b) Decreases the time complexity and increases the space complexity

(c) Increases the time complexity and decreases the space complexity

(d) Increases both, the time complexity and the space complexity

This question was addressed to me by my school principal while I was bunking the class.

Asked question is from Dynamic Programming in chapter Dynamic Programming of Data Structures & Algorithms II

Answer 1

Right answer is (b) Decreases the time complexity and increases the space complexity

The explanation is: The top-down approach uses the memoization technique which stores the previously calculated values. Due to this, the time complexity is decreased but the space complexity is increased.