Actually, my mistake is that I was examining a particular pathological case for NFAs, that DFAs handle fine:  something like &#x2F;.+aaaaaaaaaa&#x2F;.  In this case, the number of states the automaton could be in grows with the length of the input, until you hit the upper bound of &quot;all eleven states&quot;.  For that regex, the worst case is O(min(len(regex),len(input))*len(input)).  This is quadratic in the input length, until a certain point.  Which formula is correct then depends on whether the regex or the input is longer.<p>In other cases (e.g. &#x2F;(aa|ab|ac|ad|ae|af|ag|...)+&#x2F;), you blow up to the maximum number of states immediately, and for a matching string stay in the same number of states the whole time.  Therefore, it is technically correct to leave out the len(input) parameter if you are considering arbitrary regular expressions.<p>&gt; You can skirt around that with a lazy DFA<p>This adds unwarranted complexity if you&#x27;re doing ahead-of-time compilation.  Perhaps the best approach there is to try to convert the regex to a DFA, but bound the number of states to some multiple of the number of NFA states.  If you surpass this number, consult the requirements of the situation and either reject the expression or just use the NFA that was built in the process.