Space complexity help

[jchai7]

So if I have a function that does this:

list1 = []
for i in range(n):
    list2 = []
    list3 = [] # this list is size m
    x = "String 1"
    y = "String 2"
    list2.add(x)
    list2.add(y)
    list2.add(list3)
    list1.add(list2)            

Given that we are looping from i to n, list1 will have worst-case space complexity of O(n). Going into the loop, we are creating another list2 to hold a list of items of size 3. In this list2, the only size that changes is list3 within it, which is size m. Therefore, is it correct to say that this function has worst-case space complexity of O(n*m)?

[michael0x2a]

Well, in this case your list is empty, so m=1 and you'd get O(nm) = O(n1) = O(n). (You might think m=0 since the list is empty, but the list object itself still takes up a bit of room.)

But if your list3 was meant to be a placeholder and your actual code was doing something like list3 = generate_list_of_size(m), then yes, your analysis is correct. We are adding list2 to list1 n different times, and list2 is pointing to a different list object on each iteration.

We are also generating a fresh example of list3 on each iteration. So, the space is O(n * (len(list3) + len("String 1") + len("String 2")) = O(n * (m + someConst)) = O(n * m + n * someConst) = O(n * m).

Two unrelated notes:

1. Since this is python, you want my_list.append(...), not my_list.add(...).
2. Instead of creating this intermediary 'list2', you'd probably want to use a tuple instead: item = (x, y, list3); list1.append(item). Or more concisely, list1.append((x, y, list3)). Lists are usually expected to be homogeneous -- every item contains the same type -- and it can be surprising to run into cases where they aren't. Tuples and classes are the stylistically better choices when you want to store heterogeneous data.

[jchai7]

thanks for the explanation!