Какова сложность регулярного выражения?

Какова сложность относительно длины строки, необходимой для выполнения сравнения регулярных выражений в строке?