[Solved]: Why is the running time of edit distance with memoization $O(mn)$?

Problem Detail: 

I understand without memoization it is going to be $O(3^{\max\,\{m,n\}})$ because every call results in extra three calls: thus we end up having a call tree with three children for each node, with height $\max\,\{m,n\}$, m and n being lengths of two given strings.

However I am not getting why it is $O(mn)$ after memoization. Can someone please help me understand this?

I also know that, in the case of dynamic programming, the complexity will be number of distinct sub-problems we solve (because we save the solution of subproblems).

How do I calculate distinct sub-problems I am solving in Edit Distance.

P.S. I am not asking here for tabulation approach (top-down method) or explanation int the form of tabulation approach. This question on Stack Overflow contains the code of Edit Distance with memoization.

Asked By : Sandesh Kobal

Answered By : Yuval Filmus

I'm assuming $n,m$ are the lengths of the input strings. The number of sub-problems are the number of different inputs to the recursive procedure edit_distance, ignoring the memo input. You can check that s1 is always a suffix of the first input string and that s2 is always a suffix of the second input string. Since there are $n+1$ suffixes of the first input string and $m+1$ suffixes of the second input strings, the total number of sub-problems is $(n+1)(m+1) = O(nm)$.

If evaluating the body of edit_distance (minus the recursive calls) took $O(1)$, then the total running time would be $O(nm)$. However, this is actually not the case. The function make_pair and the ensuing hash take $\Theta(|s_1|+|s_2|)$, which for a majority of function calls is $\Theta(n+m)$. Therefore the running time is actually $\Theta(nm(n+m))$ rather than $\Theta(nm)$. This slowdown is avoided in the dynamic programming solution, which does run in time $O(nm)$.

($\Theta(\cdot)$ is similar to $O(\cdot)$; whereas $O(\cdot)$ is only an upper bound, $\Theta(\cdot)$ is both a lower bound and an upper bound. I need to use it here since the fact that the algorithm runs in time $O(nm(n+m))$ doesn't preclude the possibility that it actually runs in time $O(nm)$; to preclude this possibility we need a lower bound on the running time.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/34050