How much space dose list re-allocation cost in Python?

Question

I'm trying to solve a problem with O(1) in space. Could anyone help me determine if the following code is taking O(1) space?

I got a list as input and every time I ran a loop I do

list = list[:len(list)/2+1]

Does list re-allocation use the original memory of that list, or should it create extra memory usage? Thanks.

score 0 · Accepted Answer · answered Jun 02 '19 at 03:32

You can see it's a shallow copy with a simple test

list = [1,2,3,4,5,6,7,8]
list2 = list[:len(list)//2+1]

list2[0] = 999
print(list)
print(list2)

This prints

[1, 2, 3, 4, 5, 6, 7, 8]
[999, 2, 3, 4, 5]

So clearly they aren't sharing memory. This is not O(1) space

1 Answers1