1
$\begingroup$

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    }
$\endgroup$

1 Answer 1

0
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ The total number of line-executions in the answer predicts that your algorithm will run well within 1 second even if s.length =300 and p.length <= 300. $\endgroup$
    – John L.
    May 11, 2022 at 22:03
  • $\begingroup$ For a detailed introduction to dynamic programming and time-complexity analysis of it, check chapter "Dynamic Programming", Introduction to Algorithms by CLRS, where you can find many well-explained examples. $\endgroup$
    – John L.
    May 12, 2022 at 8:18
  • $\begingroup$ Thank you John for the comprehensive explanation. Could you please explain "(17−7+1)(m+1)(n+1)+3(1+4(m+1)(n+1))+2" part. $\endgroup$ May 12, 2022 at 15:56
  • $\begingroup$ @SiddharthaSadhukhan Does my updated answer explain that expression clearly? $\endgroup$
    – John L.
    May 12, 2022 at 17:12
  • $\begingroup$ Thank you John L., I had manged to compute the complexity O(mn) but failed to thought at this level. This one will be acting like a reference for my future analysis. One more thing, do we have any other way to dry-run a recursive solution except recursion tree. And thank you once again $\endgroup$ May 12, 2022 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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