Python string concatenation temporary complexity

Question

I am analyzing the complexity of my code. From what I found on the Internet, since strings are immutable in python, the string and character concatenation should be O (len (string) + 1).

Now here is my code snippet (simplified):

word = "" for i in range(m): word = char_value + word return word 

The total time complexity should be:

(0 + 1) + (1 + 1) + ... + m = m (m + 1) / 2 = O (m ^ 2)

Is it correct?

Answer 1

Yes, in your case <convey ^{* 1 you} need to copy all the characters, this is O (N + M) operation (where N and M are the sizes of the input lines). M adds the same word, will tend to O (M ^ 2) time for this.

You can avoid this quadratic behavior by using str.join() :

 word = ''.join(list_of_words) 

which only accepts O (N) (where N is the total length of the output). Or, if you repeat one character, you can use:

 word = m * char 

You add characters, but first create a list and then change it (or using the collections.deque() object to get O (1 )'s pre-empt behavior) will still be O (n) complexity, easily beating your O (N ^ 2) choice here.

---

^{* 1} As with Python 2.4, the implementation of CPython avoids creating a new string object using strA += strB or strA = strA + strB , but this optimization is fragile and not portable. Since you are using strA = strB + strA (append), optimization is not applied.