&gt; Not constant, bounded.<p>If I can do this:<p><pre><code>    re = regexp(&quot;.+aaaaaaaaaaa&quot;)
    state = malloc(len(re))
    match1 = exec(re, &quot;aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa&quot;)
    match2 = exec(re, &quot;aaa&quot;)
    match3 = exec(re, &quot;aaaaaaaaaaa&quot;)
    ...
</code></pre>
And I also claim that `exec` is guaranteed to <i>never</i> call `malloc` in any of its executions (or otherwise allocate).<p>Do you consider that constant or bounded? It looks like it&#x27;s constant to me.<p>If you&#x27;re talking about CPU resources, then the absolute worst case in the NFA algorithm is requiring `len(re)` operations per position in the input. I guess this is what you&#x27;re referring to as bounded? If so, then it is a linear bound. :-) An attacker can&#x27;t make matching take more than linear time.<p>I feel like this entire conversation has been one roundabout exploration of &quot;DFAs are faster than NFAs.&quot; :-&#x2F;<p>&gt; I also didn&#x27;t sufficiently reconsider the expression when I realized this: the terminal anchor is quite relevant, but I forgot it was there. In reality you&#x27;re correct about this with the convention you are using.<p>You had me doubting myself there for a second, so kudos. :-)