CODEWITHSUNDEEP
time-complexitydynamic-programming
piyush172
piyush172

Reputation: 100

Time Complexity comparision of memoized recursion and table method in Dynamic programming

Does every code of Dynamic Programming have the same time complexity in a table method or memorized recursion method?

A Solution with an appropriate example would be appreciated.

Upvotes: 1

Views: 638

Answers (1)

sspathare97
sspathare97

Reputation: 343

Time complexity- Yes (if you ignore the function calls/returns in Memoization)
Space complexity- No. Tabulation can save space by overwriting previously calculated but no longer needed values.

As mentioned in the "Optimality" section of this answer- https://stackoverflow.com/a/6165124/7145074

Either approach may not be time-optimal if the order you happen (or try to) visit subproblems is not optimal, specifically if there is more than one way to calculate a subproblem (normally caching would resolve this, but it's theoretically possible that caching might not in some exotic cases). Memoization will usually add on your time-complexity to your space-complexity (e.g. with tabulation you have more liberty to throw away calculations, like using tabulation with Fib lets you use O(1) space, but memoization with Fib uses O(N) stack space).

Further reading- https://www.geeksforgeeks.org/tabulation-vs-memoization/

Upvotes: 2

Related Questions