&gt; Yes, there is a bound to the number of operations of 11{star}length. Yes, this means that big-O says it&#x27;s linear.<p>... that&#x27;s been exactly my position this entire time.<p>I guess I just don&#x27;t understand why you are calling the NFA algorithm quadratic. Calling it quadratic because there exists a particular progression that moves the runtime complexity in a quadratic fashion up to a predetermined <i>linear</i> bound seems <i>really</i> confusing.<p>Overall, attackers can&#x27;t make the entire algorithm run in quadratic time in the length of the input or the regex. That&#x27;s what matters.<p>With all that said, I agree with your final conclusion of course, that the NFA algorithm is going to be slower than running a pre-built DFA. But I think attributing this to quadratic behavior is just confusing. I personally think of it more as the NFA having to maintain multiple simultaneous states and being forced to follow epsilon transitions over and over again. In contrast, a DFA will only ever be in one state and it will cache all of the epsilon transitions in its states.<p>&gt; An attacker still has significant control over system resource usage in a way that he would not with a constant-resource approach.<p>Cox&#x27;s formulation very explicitly provides an implementation of the NFA algorithm that uses constant resources (with respect to the input).<p>I mean, this isn&#x27;t theoretical. You can go look at an implementation of the NFA algorithm by either Cox or myself, and it&#x27;s pretty clear that some fixed allocation (based on the size of the compiled regex) happens up front, and no further allocation happens during the actual search. You can&#x27;t make it blow up and take quadratic time.<p>&gt; This isn&#x27;t even one of them, however, because the NFA has no loop. 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.<p>It&#x27;s exponential because it requires counting. You don&#x27;t actually know <i>when</i> you&#x27;ve seen the initial zero, since you can see any number of 0s or 1s before it, and exactly N number of 0s or 1s after it, and then following that, the end of the string. (That final `$` is probably crucial to requiring an exponential number of states.)<p>It&#x27;s a pretty standard example: <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Regular_expression#Expressive_power_and_compactness" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Regular_expression#Expressive_...</a><p>See also: <a href="https:&#x2F;&#x2F;github.com&#x2F;google&#x2F;re2&#x2F;blob&#x2F;master&#x2F;re2&#x2F;testing&#x2F;dfa_test.cc#L166" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;google&#x2F;re2&#x2F;blob&#x2F;master&#x2F;re2&#x2F;testing&#x2F;dfa_te...</a><p>This blurb from Wikipedia is also relevant:<p>&gt; On the other hand, it is known that every deterministic finite automaton accepting the language Lk must have at least 2k states. Luckily, there is a simple mapping from regular expressions to the more general nondeterministic finite automata (NFAs) that does not lead to such a blowup in size; for this reason NFAs are often used as alternative representations of regular languages.<p>This exactly matches my experience and what Cox says.