This result has always been a bit of a head-scratcher for me, in that it seems to require that we increase the pattern size (specifically, the number of back-references). While the result is correct, it seems to run counter to common usage of regular expressions, where the regular expression is fixed and the interest is generally in how fast a given regular expression runs over N bytes of input data.
It feels a bit like informing people that comparing two integers is O(N) because maybe the integers are bignums with N bits each; true, but counter to common usage.
It feels a bit like informing people that comparing two integers is O(N) because maybe the integers are bignums with N bits each; true, but counter to common usage.