title: Complexity of Regex substitution
body: <p>I didn't get the answer to this anywhere. What is the runtime complexity of a Regex match and substitution?</p>
  
  <p>Edit: I work in python. But would like to know in general about most popular languages/tools (java, perl, sed).</p>