title: Is the time-complexity of iterative string append actually O(n^2), or O(n)?
body: <p>I am working on a problem out of CTCI.</p>
  
  <p>The third problem of chapter 1 has you take a string such as </p>
  
  <p><code>'Mr John Smith    '</code></p>
  
  <p>and asks you to replace the intermediary spaces with <code>%20</code>:</p>
  
  <p><code>'Mr%20John%20Smith'</code></p>
  
  <p>The author offers this solution in Python, calling it O(n):</p>
  
  <pre><code>def urlify(string, length):
      '''function replaces single spaces with %20 and removes trailing spaces'''
      counter = 0
      output = ''
      for char in string:
          counter += 1
          if counter &gt; length:
              return output
          elif char == ' ':
              output = output + '%20'
          elif char != ' ':
              output = output + char
      return output
  </code></pre>
  
  <p>My question:</p>
  
  <p>I understand that this is O(n) in terms of scanning through the actual string from left to right. But aren't strings in Python immutable? If I have a string and I add another string to it with the <code>+</code> operator, doesn't it allocate the necessary space, copy over the original, and then copy over the appending string?</p>
  
  <p>If I have a collection of <code>n</code> strings each of length 1, then that takes:</p>
  
  <p><code>1 + 2 + 3 + 4 + 5 + ... + n = n(n+1)/2</code></p>
  
  <p>or <strong>O(n^2) time</strong>, yes? Or am I mistaken in how Python handles appending?</p>
  
  <p>Alternatively, if you'd be willing to teach me how to fish: How would I go about finding this out for myself? I've been unsuccessful in my attempts to Google an official source. I found <a href="https://wiki.python.org/moin/TimeComplexity" rel="noreferrer">https://wiki.python.org/moin/TimeComplexity</a> but this doesn't have anything on strings.</p>