Complexity in Top-Down Approach

Revision en1, by -synx-, 2017-05-01 15:37:40

Can we figure out the complexity of a DP solution (recursion + memoization, ie top-down) for a particular problem.
This might look to be a very general question. What I am implying is, if a particular problem cannot be thought up easily in a bottom up manner (where knowing complexity is easier), then how can we ascertain the complexity of the dp solution.
Fibonacci for example can be calculated via
1. Bottom Up: f[i] = f[i - 1] + f[i - 2]
It is easy to see the complexity would be O(n).
2. Top Down: f(n) = f(n - 1) + f(n - 2)
Recursively, the complexity is On) which will be reduced to O(n) with memoization (by knowing the distinct states).
So, is their always a relation between complexity of top-down and the distinct states/subproblems, which can be figured out?

Tags dp, top-down, algorithm complexity


  Rev. Lang. By When Δ Comment
en1 English -synx- 2017-05-01 15:37:40 831 Initial revision (published)