The time-complexity of dynamic-programming with memoization
Here is the simple principle. Suppose an algorithm
- applies dynamic programming to solve a problem,
- with the majority of running time spent on computing $O(s)$ subproblems for some expression $s$,
- where each subproblem is computed only once thanks to memoization,
- and it takes $O(u)$ time for some expression $u$ to compute each subproblem, assuming it takes $O(1)$ time to access the result of any other subproblems that are needed during that computation,
then the time-complexity of the algorithm is $O(su)$, in general.
Analysis of the algorithm in the question
Let $m$ be the length of the string and $n$ be the length of the pattern. So there are $(m+1)(n+1)$ entries in the table dp. (They represent $O(mn)$ subproblems.)
The code that actually computes and updates the entries are the code block from line 7 to line 17. Because of memoization, these lines will be executed at most once for each entry. So these lines will be executed at most $(m+1)(n+1)$ times.
How many times will line 4 (for building and quitting calling stack frames), line 5 and 6 be executed? Except the very first time that is triggered by line 2, the execution of them are triggered by line 9, 10, 12, or 15, which is, in turn, triggered by the execution of the code block mentioned above. So line 4, 5 and 6 are executed at most $1 + 4(m+1)(n+1)$ times.
So, the total number of line-executions of the algorithm is at most $$(17-7+1)(m+1)(n+1) + 3(1 + 4(m+1)(n+1)) + 2,$$ where the last number $2$ is for line 1 and 2. We can check that it takes $O(1)$ time to execute each line. Hence, the time-complexity of the algorithm is $O(mn)$.
The analysis above serves as an example to illustrate and validate the principle.
Or we can apply the principle directly. There are $O(mn)$ subproblems. It takes $O(1)$ time to compute each subproblem, ignoring the time for the recursive calls to obtain results of other subproblem. Hence the time-complexity of the total algorithm is $O(mn\times 1) = O(mn)$.