CODEWITHSUNDEEP
recursiontime-complexitydynamic-programmingmemoizationknapsack-problem
Ankur Solanki
Ankur Solanki

Reputation: 21

Dynamic programing: Tabular vs memoization

Is the time complexity of dynamic programming tabular approach and recursion with memoization approach the same? For example, in the Knapsack problem the tabular approach takes O(N*W) where N is the number of items and W is the weight. But what is the time complexity for the memoization approach?

Upvotes: 2

Views: 3458

Answers (2)

smalik
smalik

Reputation: 373

Is the time complexity of dynamic programming tabular approach and recursion with memoization approach the same?

Yes the do have same time complexity of O(N*W) where N is the number of items and W is the weight. However, If the original problem requires all subproblems to be solved like in the case of Knapsack problem,

tabulation usually outperformes memoization by a constant factor.

This is because tabulation has no overhead for recursion and can use a preallocated array rather than, say, a hash map.

What is the difference between tabulation and memoization?

When you solve a dynamic programming problem using tabulation (generally iterative) you solve the problem "bottom up", i.e., by solving all related sub-problems first, typically by filling up an n-dimensional table. Based on the results in the table, the solution to the "top" / original problem is then computed.

If you apply memoization (generally recursive) to solve the problem you do it by maintaining a map of already solved sub problems. You do it "top down" in the sense that you solve the "top" problem first (which typically recurses down to solve the sub-problems).

Which is better? Memoizaiton or tabulation?

If we don’t require to solve all the problems and are just looking for the optimal solution, memoization is better. If we do require to solve all the problems, that means we are going to make numerous recursive calls which may fill the stack space respectively, and there tabulation is better.

The caveat is that memoization is generally more intuitive to implement especially when we don’t know the solution to subproblems, whereas tabulation requires us to know the solutions, or bottom, in advance, in order to build our way up.

Useful Resources:

What is Dynamic Programming? Memoization and Tabulation
Tabulation vs Memoization

Upvotes: 2

Amihay Elboher
Amihay Elboher

Reputation: 21

Memoization is a method used to solve dynamic programming (DP) problems recursively in an efficient manner. DP abstracts away from the specific implementation, which may be either recursive or iterative (with loops and a table). Therefore, if used appropriately, the time complexity is the same, i.e. O(NW) in the knapsack problem over the integers.

This is what we used in introduction to CS and algorithm design courses in BGU (I was a T.A. in both if matters), but there might be other terminologies which I'm unaware of.

I hope it was helpful, good luck!

Upvotes: 1

Related Questions