First of all, this is why people should stop adding stupid features to regular expressions. A sane regular expression implementation has <i></i>no<i></i> pathological cases. DFA generation can be done in O(n^2) from memory (in the absolute worst case O(n) is average), and matching can&#x27;t be worse than O(m) or similar (n is the size of the regex and m the size of the string). When you add features like back references and recursive matches, you bring the worst case complexity to O(a^n), which is exponential.<p>And why? So you could write some dirty hack rather than writing a simple recursive descent parser to create an AST of the code (which takes O(n)). What did you gain by ruining your regular expression implementation and writing shitty code?<p>EDIT: Matching <i>might</i> be O(m), but I&#x27;m wondering about maximally linked graphs with many epsilon edges. The conversion from DFA to NFA would require O(n^2) in that case. Implementing it as an NFA evaluation might be faster than full conversion, but then you run the risk of having O(n^2) dominating in the matching.<p>EDIT: The author is somewhat correct on what &quot;catastrophic back referencing&quot; is. While you could argue that it is due to bad implementations of the greedy matching, it&#x27;s a more endemic problem of how you have to implement a regular expression engine that supports back references. If you have to support back references, then you will always have a class of pathological cases which cause exponential time complexity. I had a useful graph about this on my toy regular expression engine (which performs much better than Python&#x27;s implementation even though it&#x27;s written in Python and not C): <a href="https:&#x2F;&#x2F;github.com&#x2F;cyphar&#x2F;redone" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;cyphar&#x2F;redone</a>.