6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You want an $\Omega$ in the first line? $\endgroup$ – Raphael Dec 9 '14 at 10:08
  • $\begingroup$ Oh Yes it should be max{m,n} for O and min{m,n} for Ω $\endgroup$ – Sandesh Kobal Dec 10 '14 at 2:14
1
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.