2 ms·
That blow up is quadratic, not exponential: "This is not classic catastrophic backtracking (talk on backtracking) (performance is O(n²), not exponential, in len
by isaacg 7y ago
That blow up is quadratic, not exponential: "This is not classic catastrophic backtracking (talk on backtracking) (performance is O(n²), not exponential, in length), but it was enough."
- perlgeek 7y agoSome years ago I tried to create an exponential time regex in Perl, and only managed a quadratic time one after a bit of experimenting. But, as you said, quadratic is often already fatal on realistic data.