What is the complexity of regular expression?
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.