title: Does str.replace() have a time complexity O(n^2)?
body: <p>I am trying to find the time complexity of <code>str.replace()</code> built into python, and this is the data I've managed to gather (here and on other sites):</p>
  <p>I know <code>replace()</code> is based on the Boyer–Moore algorithm, which takes worst-case time of O(n*m) to find a substring, but is this for a <strong>single</strong> substring?</p>
  <p>Does <code>replace()</code> return a copy of the &quot;fixed&quot; string when it finds the first substring and then start to search again?</p>
  <p>And what about when we have <strong>multiple</strong> occurrences of a substring, like the following example:</p>
  <pre><code>old_string = '192.168.1.1'
  new_string = old_string.replace('.', '|')
  </code></pre>
  <p>If it can only replace one substring at a time, then for a single substring we get O(n*m), times the number of substrings which is a maximum of n/m. This comes to O(n^2)!</p>
  <p>Given that a simple loop would take O(n), like:</p>
  <pre><code>old_string = '192.168.1.1'
  new_string = []
  for ch in old_string:
      new_string.append('|' if ch == '.' else ch)
  </code></pre>
  <p>Does that make sense? Am I missing something?</p>
  <p>Could the built in replace() be flawed for multiple replacements, or is it implemented in a way to continue where it left off?</p>