What is the complexity with respect to the string length that takes to perform a regular expression comparison on a string?
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.
N
O(N)
You may find the following document of interest: Regular Expression Matching Can Be Simple And Fast.
1.4m articles
1.4m replys
5 comments
56.9k users