1
$\begingroup$

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

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.

$\endgroup$
  • 1
    $\begingroup$ There are many examples for which this is not the case. What research have you done? $\endgroup$ – Raphael Jun 4 '16 at 15:20
  • $\begingroup$ The first item in my answer applies to recursive implementations as well. $\endgroup$ – Raphael Jun 4 '16 at 16:26
3
$\begingroup$

There are plenty examples for which you

  • need $\omega(1)$ time to compute each table entry or
  • do not need to keep all table entries.

An example for the former would be CYK; for the latter memoized Fibonacci and Bellman-Ford.

$\endgroup$
2
$\begingroup$

This is not a general rule. It is very possible for a dynamic programming algorithm to have greater time complexity than space complexity (but obviously not the other way around, since we spend at least $O(1)$ time per instance).

For instance, you mention that the dice sum problem can be solved in $O(D*T)$ time and space (if we let $D$ be the number of dice and $T$ be the target sum). It can also be solved in $O(D*T)$ time and $O(T)$ space, simply by noting that the computation of the values follows a specific pattern and that to compute the answer for $n$ dice, you only need the answers for $n$ and $n-1$ dice (and you can forget the answers for $n-2,n-3,\ldots$ dice).

$\endgroup$
  • $\begingroup$ Tom, have solved the Dice problem with that Space complexity iteratively by building up a matrix and only keeping a row, but not recursively with memoization. Are you saying that recursively with memoization you can only keep a partial set of the data table ? How would you set up the algorithm ? $\endgroup$ – Fairly Nerdy Jun 4 '16 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.