What is the space complexity of a list in a while loop?

Question

I believe that a similar question has been asked for Java but I'm not sure whether the same applies to Python since we don't explicitly use the new keyword

For this particular code:

x = 5
while (x > 0):
  arr = []
  arr2 = []
  arr.append(1)
  arr2.append(2)
  x -= 1

After executing this code, will there be a total of 10 different lists being created, which is a space complexity of O(10), or will there only be 2 lists being created, which is a space complexity of O(2). I understand the overall space complexity is still O(1) but just wanted to find out what happens under the hood.

Answer 1

Firstly, since you wrote arr = [] inside the while loop it will rewrite the previous array, hence both arr and arr2 will have at most 1 element

Secondly, with the formal definition of Big-O complexity O(1) and O(2) are considered the same constant-complexity, Big-O complexity is meant to be used with a variable to capture complexity relative to a variable.

If you want to know whether or not python creates a new array with your code, you can override the default list object to log it's operations:

class ilist(list):
    def __init__(self, r=list()):
        print("Making new list: " + str(r))
        list.__init__(self, r)

    def __del__(self):
        print("Deleting list")


x = 5
while (x > 0):
    arr = ilist()
    arr2 = []
    arr.append(1)
    arr2.append(2)
    x -= 1
print("Finished while")

output:

Making new list: []
Making new list: []
Deleting list
Making new list: []
Deleting list
Making new list: []
Deleting list
Making new list: []
Deleting list
Finished while
Deleting list

and as you can see it indeed creates and deletes the array every time since that array is created and used only inside the block of while. But it behaves as it should, if your intention was to create it once, then you should declare it in the outer scope.