&gt; It&#x27;s guaranteed O(mn) time.<p>I&#x27;m apparently completely failing to communicate my point here, because you seem to think I&#x27;m contradicting this.  I am not.  I&#x27;ll maybe try to work through the example.  For the purposes of this example, we have a <i>fixed</i> regular expression of &#x2F;.+aaaaaaaaaa&#x2F;.<p>Processing the string &#x27;a&#x27; takes one operation.  Processing the string &#x27;aa&#x27; takes three operations.  Processing the string &#x27;aaa&#x27; takes six operations.  Processing a string of &#x27;aaaa&#x27; takes ten operations.  This is a quadratic progression.  The DFA, however, has only eleven states.<p>Yes, there is a bound to the number of operations of 11*length.  Yes, this means that big-O says it&#x27;s linear.  No, an attacker can&#x27;t simply supply a 30-character string and lock up your system the way they might be able to for a backtracking approach.  That&#x27;s beside the point.  An attacker still has significant control over system resource usage in a way that he would not with a constant-resource approach.  An attacker may still be able to exploit this in a way that would not be an issue with a DFA, e.g. by attempting to exhaust memory by issuing many simultaneous expensive requests when your system is provisioned to handle average requests.<p>&gt; Offline DFAs do, however, have pathological cases where the number of states required is exponential. For example, `0[01]{n}$`, has an exponential number of states proportional to 2^n.<p>Yes, there are pathological cases, which is why you don&#x27;t use that approach with untrusted regexes.  I&#x27;ve never disagreed with this.<p>This isn&#x27;t even one of them, however.  The DFA would have n+3 states:  an initial state, a reject-loop state, a state for when we have seen the initial zero, and one state for when we have seen each of n additional zeroes or ones.  I&#x27;m not sure how one would end up with more states than that:  perhaps by not consolidating equivalent states in the NFA first?<p>Edit:  Apparently you&#x27;re using the convention that one searches for a match anywhere in the input string, which while common isn&#x27;t what I&#x27;m used to.  This doesn&#x27;t change anything:  it just makes most transitions that would otherwise go to the reject-loop state go to the initial state instead.<p>It&#x27;s possible to get a pathological DFA, but one needs to work harder at it than this.