Time complexity analysis for dynamic programming using memoization

Question

I am trying to figure out the time complexity for "Regular Expression Matching" problem. Problem statement is simple, only meta characters allowed are '.' and '*'. Actual problem statement can be found in Link

The solution is in java and I have solved it using memoization, but having difficulty to compute the time complexity. Can anyone help me with the explanation, and any reference documents or link to study further on this subject.

 1    public boolean isMatch(String s, String p) {
 2        return backTrack(s, 0, p, 0, new Boolean[s.length() + 1][p.length() + 1]);
 3    }
    
 4    boolean backTrack (String s, int si, String p, int pi, Boolean[][] dp) {
 5        if (pi >= p.length()) return si >= s.length();
 6        if (dp[si][pi] != null) return dp[si][pi];
 7        if (pi < p.length() - 1 && p.charAt(pi + 1) == '*') {
 8            if (si < s.length() && (s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '.')) {
 9                if (backTrack(s, si + 1, p, pi + 2, dp)) return dp[si][pi] = true; 
10                if (backTrack(s, si + 1, p, pi, dp)) return dp[si][pi] = true;  
11            }
12            if (backTrack(s, si, p, pi + 2, dp)) return dp[si][pi] = true;
13        }
14        if (si < s.length() && (s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '.')) {
15            if (backTrack(s, si + 1, p, pi + 1, dp)) return dp[si][pi] = true;  
16       }
17        return dp[si][pi] = false;  
18    }

Answer 1

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/solved only once thanks to memoization,
• and it takes $O(u)$ time for some expression $u$ to compute/solve 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 us estimate how many line-executions are done if the algorithm is run upon an input of a string of length $m$ and a pattern of length $n$.

There are $(m+1)(n+1)$ entries in the table dp (which 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 $17-7+1$ lines will be executed at most $(m+1)(n+1)$ times, i.e., these lines correspond to at most $(17-7+1)(m+1)(n+1)$ line-executions.

How many times will line $4$ (for building and quitting calling stack frames), line $5$ and $6$ be executed? Except the first time that is triggered by line $2$, the execution of them is triggered by the execution of any one of $4$ lines, line $9$, $10$, $12$, or $15$, which happens during 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, i.e., these $3$ lines correspond to at most $3(1 + 4(m+1)(n+1))$ line-executions.

So, the total number of line-executions 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 the one-time execution of line $1$ and $2$ at the start of running the algorithm. We can check that it takes $O(1)$ time to execute each line, except for possibly line $2$, which is executed once that costs up to $O(mn)$ time. 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 solve each subproblem, considering all recursive calls as taking $O(1)$ time. Hence the time-complexity of the total algorithm is $O(mn\times 1) = O(mn)$.