Qual é a complexidade da expressão regular?

Qual é a complexidade em relação ao tamanho da string que leva para realizar uma comparação de expressão regular em uma string?

unbounded – você pode criar uma expressão regular que nunca termina, em uma string de input vazia.

Se você usa normal (TCS: sem backreference, concatenação, alternação, estrela de Kleene) regexp e regexp já está compilado, então é O (n).

Se você está procurando limites assintóticos apertados no RegEx (sem respeito à expressão em si), então não há um. Como Alex aponta, você pode criar um regex que seja O (1) ou um regex que seja Omega (infinito). Como um algoritmo puramente matemático, um mecanismo de expressão regular seria complicado demais para realizar qualquer tipo de análise assintótica formal (além do fato de que tal análise seria basicamente inútil).

A taxa de crescimento de uma determinada expressão (desde que, na verdade, constitui um algoritmo, de qualquer forma) seria muito mais significativa, embora não necessariamente mais fácil de analisar.