Space complexity of method using join()

Question

Consider the following method:

def fun(lst) : 
    concat = "".join(lst) 
    return hash(concat) 

What is the place complexity of this code?
Thanks!

Answer 1

When given a list or tuple, join only allocates a constant amount of space beyond what's necessary to hold the joined string. (If not given a list or tuple, it will turn the input into a tuple, which takes O(N) space.) Since the joined string takes O(N) space, where n is the size of the input, join has O(N) space complexity.

To elaborate: join adds up the lengths of all strings to join, allocates a string big enough to hold the result, and then copies the input strings into the result. It needs to be able to iterate over the input twice to do this, so if the input isn't a list or tuple, it makes a tuple. Supposing there are n input strings of total size N, the tuple takes space proportional to n, and making the output string takes space proportional to N. If the input strings only come into existence when the tuple is created, perhaps because join was passed a generator, materializing the input strings takes space proportional to N. Thus, the total space required is O(N).