-synx-'s blog

By -synx-, history, 5 years ago,

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?

• +19

 » 5 years ago, # |   +3 Can someone throw some light on the same? Help, appreciated.
 » 5 years ago, # |   0 Let number of distinct function calls in a top down dp(recursion with memoization) be x.Let the complexity of work done inside the function be y.Then complexity of the dp solution would be x times y For example consider the following codeint func(int i,int j ){ if(i==n||j==m) return 1; else if(dp[i][j]==-1){ for(it=1;it<=k;it++){ dp[i][j]+=func(i+1,j)+func(i,j+1); } return dp[i][j]; }}let us call the function first time as func(1,1);in this case number of distinct function calls equals n*mComplexity of work done inside the function body equals O(k)Hence overall complexity of the dp solution is O(k)*(n*m)