tl;dr ''.join(string_array) is O(length of final value) in time

I do my technical interviews in python.

Today in an interview I used the ''.join(string_array) operation seen in a lot of python string manipulation algorithms and was asked for the runtime. My educated guess says O(n), but I wasn’t 100% sure.

link to answer

String concat

s = ""
for x in items:
    s += x

Python interpreter allocates memory and copies the two strings in one after the other. On many consecutive concat’s, that’s a lot of allocations.

String join

s = "".join(items)

Two iterations over items:

  • one iteration to compute total length of joined string
  • one iteration to copy each item of items into new memory