I, Philip Guenther <guenther+mtafilters(_at_)sendmail(_dot_)com> wrote:
...
For an NFA, the setup is O(N) in time and space and matching is O(N*M).
For a non-lazy DFA, the matching is O(M), but the worst-case setup is
O(2^N).
...
I should note that the dragon book's statements, as I tried to
summarize above, are only true of the original, truly regular
"regular expressions" and not the extended or 'irregular' regular
expressions seen in most tools.
In particular, counted repetitions ({n,m}) have to be expanded when
figuring the 'N' of the size of the regexp, while back-references
(\digit) are, IIRC, worst-case exponential to match. If you're
capturing matches then the POSIX matching rules apparently are
worst-case exponential on the number of characters in the regexp,
or something like that.
Philip Guenther