-synx-'s blog

Complexity in Top-Down Approach
By -synx-, history, 8 years ago, In English

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 O(φn) 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?

  • Vote: I like it
  • +19
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone throw some light on the same? Help, appreciated.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 code

int 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*m

Complexity of work done inside the function body equals O(k)

Hence overall complexity of the dp solution is O(k)*(n*m)

→ Reply