What is the complexity of regular expression?

If you use normal (TCS:no backreference, concatenation,alternation,Kleene star) regexp and regexp is already compiled then it's O(n).

The answer depends on what exactly you mean by "regular expressions." Classic regexes can be compiled into Deterministic Finite Automata that can match a string of length N in O(N) time. Certain extensions to the regex language change that for the worse.

You may find the following document of interest: Regular Expression Matching Can Be Simple And Fast.

unbounded - you can create a regular expression that never terminates, on an empty input string.