Is the time-complexity of iterative string append actually O(n^2), or O(n)?

Question

I am working on a problem out of CTCI.

The third problem of chapter 1 has you take a string such as

'Mr John Smith '

and asks you to replace the intermediary spaces with %20:

'Mr%20John%20Smith'

The author offers this solution in Python, calling it O(n):

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 > length:             return output         elif char == ' ':             output = output + '%20'         elif char != ' ':             output = output + char     return output 

My question:

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 + operator, doesn't it allocate the necessary space, copy over the original, and then copy over the appending string?

If I have a collection of n strings each of length 1, then that takes:

1 + 2 + 3 + 4 + 5 + ... + n = n(n+1)/2

or O(n^2) time, yes? Or am I mistaken in how Python handles appending?

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 https://wiki.python.org/moin/TimeComplexity but this doesn't have anything on strings.

Answer 1

In CPython, the standard implementation of Python, there's an implementation detail that makes this usually O(n), implemented in the code the bytecode evaluation loop calls for + or += with two string operands. If Python detects that the left argument has no other references, it calls realloc to attempt to avoid a copy by resizing the string in place. This is not something you should ever rely on, because it's an implementation detail and because if realloc ends up needing to move the string frequently, performance degrades to O(n^2) anyway.

Without the weird implementation detail, the algorithm is O(n^2) due to the quadratic amount of copying involved. Code like this would only make sense in a language with mutable strings, like C++, and even in C++ you'd want to use +=.