For a given piece of text, pattern-matching is (if P!=NP) exponential in the number of back-references (one measure of "size of the pattern"), in the general non-lucky cases of patterns.
This seems plausible, but is the inverse of the traditional expectation of what grows and what stays the same. I refer only to a pragmatic experience of regex implementation (as opposed to a theoretical refutation of the point) - the size of the pattern is typically a constant and the metric of interest is usually the difficulty of scanning a fixed pattern over an arbitrary and increasing-sized input buffer with worst case input.