Simple regexes can be reasonably quick, but you're almost certainly never going to do better than linear time, and if you get fancy, it's easy to go exponential with a large exponent.
If you want to guarantee that this will never happen, RE2 and similar regular expression engines are guaranteed to run in O(n) time, where n is the length of the target string.
