&gt; This will lead to quadratic runtime and linear additional memory usage up to the bound of the number of states in the NFA.<p>If by quadratic runtime you mean O(len(regex) * len(input)), then fine. (I think it&#x27;s a bit strange to call that quadratic, since the size of the regex is constant.) If by quadratic runtime, you mean O(len(input)^2)), then I contest that. My guess is that you probably do indeed mean the former.<p>And certainly, &quot;linear additional memory usage&quot; is not relative to the input either.<p>&gt; There is a key insight there: that it is in fact bounded, and you can plan around these bounds. It&#x27;s not the tight constraint a DFA gives you (where the number of operations is constant, and runtime varies only by hardware details like L1 cache misses), but it&#x27;s still good enough for most cases.<p>Sure, but now you have to deal with exponential state blow up. :-)<p>You can skirt around that with a <i>lazy</i> DFA, and you&#x27;re now technically back to O(mn) (same as the NFA algorithm in the worst case), but in the common case, you end up pretty close to the performance of a DFA constructed offline.<p>As &quot;evidence&quot; of my claim, you might peruse these unscientific benchmarks: <a href="https:&#x2F;&#x2F;github.com&#x2F;jneem&#x2F;regex-benchmarks" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;jneem&#x2F;regex-benchmarks</a> (The first group uses an offline DFA and the latter two groups are both lazy DFAs. Of course, this is just an anecdote!)<p>My view on this is pretty biased because my goal is not to just be able to deal with untrusted input, but to also deal with untrusted regexes. It&#x27;s hard to satisfy the latter case with an offline DFA. :-&#x2F;