I am studying Dynamic Programming using both iterative and recursive functions. With recursion, the trick of using Memoization the cache results will often dramatically improve the time complexity of the problem.
When evaluating the space complexity of the problem, I keep seeing that time O() = space O(). This is because we will have to cache all the results, but once we cache them it is O(1) to retrieve
Examples of this are
- Dice Sum Problem - count the number of ways N dice can roll a certain Sum. Time O(num dice * target Sum) Space O(num dice * target Sum) https://stackoverflow.com/questions/19719439/calculate-the-number-of-ways-to-roll-a-certain-number
- Coin Change Problem - count number of ways to make change for a certain money amount given a list of coins. Time O(num coin denominations * value to make change from) Space - same as time https://stackoverflow.com/questions/28910971/dynamic-programming-coin-change-problems
My question is, with Memoization, will the space & time complexity always be the same ? If not, why not ?
Edit - Clarification
This question is regarding the Space complexity of the recursive solution. I have solved the iterative solution using smaller space complexity before, i.e. keeping only a single row in the matrix. However for the recursive solution, I have never seen a recursive approach where items are deleted from the memoization table. I suppose you could combine recursion + iteration to only keep a single row in the memoization, but I have not seen an example where you start at the pure end, and only keep limited space.