While that&#x27;s technically correct (the number of states in the NFA represents an upper bound on the number of states the simulation can be in at a time), this is one of those times when big-O can be misleading.  In practice, there&#x27;s a lot of variation between inputs.  A typical case will leave you in only a handful of states at once, but a carefully constructed input can put you into many states.  This will lead to quadratic runtime and linear additional memory usage up to the bound of the number of states in the NFA.<p>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.