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
