''.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.
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.
s = "".join(items)
Two iterations over
- one iteration to compute total length of joined string
- one iteration to copy each item of
itemsinto new memory