I think it's more that you need to give the O(n) of your answer, which is generally very difficult to do with regex. And even if it's possible, it might not be an acceptable O(n).

In general regexes finish instantly for normal sized inputs, but the actual O(n) might be quadratic or whatever.