3 ms·
Depends on what you mean by that. You can convert every NFA into a DFA. That's a NP complete (IIRC), but running the DFA is O(n). Running the NFA without conver
by tgv 5mo ago
Depends on what you mean by that. You can convert every NFA into a DFA. That's a NP complete (IIRC), but running the DFA is O(n). Running the NFA without converting it is also NP complete. One isn't better than the other, but the costs vary for different expressions and usages.
- DmitryOlshansky 5mo agoRunning NFA is O(nm) not NP.
- benchloftbrunch 5mo agoSo it is NP (in fact P)
- tgv 5mo agoSorry, you're right. Capturing worst case was much more expensive, I believe, but I'm no longer sure.