Turn an NFA into a DFA by naming each reachable state-set as one DFA state, then watch the conversion stay cheap until a pattern makes the state count double toward 2 to the n.

Run `ab|ac` through the NFA and the engine juggles a live set of states on every character, the cloud you watched last topic. Now imagine drawing every cloud it could ever form, once, before a single character arrives.

Sort the real engines into the two families that either compile a machine or explore choices, see why one can never hang while only the other supports backreferences, and pick the family a given constraint demands.

The pattern `\d{4}` runs about the same speed on every engine you try. Swap in `(a+)+$` over a long run of letters and one engine answers in microseconds while another climbs past a full minute, same input, same regex.