No, it can&#x27;t happen at all. After processing the first state that visits all states on input i, all subsequent states explored in input i stop before traversing states that have already been visited. Since all states have already been visited, each state after the first on input i can be dismissed in constant time. Given that one can check whether a state has been visited in constant time, this is still just linear, not quadratic.<p>Let&#x27;s just look at code already.<p>Here&#x27;s the loop over states at input i: <a href="https:&#x2F;&#x2F;github.com&#x2F;rust-lang-nursery&#x2F;regex&#x2F;blob&#x2F;master&#x2F;src&#x2F;nfa.rs#L165" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;rust-lang-nursery&#x2F;regex&#x2F;blob&#x2F;master&#x2F;src&#x2F;n...</a><p>If we match a character at input i, then we follow epsilon transitions: <a href="https:&#x2F;&#x2F;github.com&#x2F;rust-lang-nursery&#x2F;regex&#x2F;blob&#x2F;master&#x2F;src&#x2F;nfa.rs#L237" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;rust-lang-nursery&#x2F;regex&#x2F;blob&#x2F;master&#x2F;src&#x2F;n...</a><p>If we visit a state that we&#x27;ve already seen, skip it: <a href="https:&#x2F;&#x2F;github.com&#x2F;rust-lang-nursery&#x2F;regex&#x2F;blob&#x2F;master&#x2F;src&#x2F;nfa.rs#L300" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;rust-lang-nursery&#x2F;regex&#x2F;blob&#x2F;master&#x2F;src&#x2F;n...</a><p>If that first state visits all states, then `nlist` (which is maintained while following all states at any position in the input) will contain all states. In each subsequent iteration (line 165), even if the state wants to visit all states, it will be immediately stopped at the first check in line 300. No additional states for that state are followed.