Isn't it O(n) where n is the length of the string to match? Because you can compile any regex to a DFA and run it over the string.