My book says "As the length of a list grows, the number of references stored in it grows linearly, but memory needed to store a reference to the list's contents stays the same." What does this mean? Is the space complexity O(n) or O(1) as the list size increases?

CodePudding user response：

If you create a list l = [1,2] then create another reference to it l2 = l. l2 shares the data [1,2]. You can see that by changing l2[0] = 3 then l[0] is now also 3:

l = [1,2]
l2 = l
l2[0] = 3
print(l)
[3,2]

The references l and l2 are of O(1) space which means for sufficiently large n it requires no more than k space per reference. The data itself O(n) so for sufficiently large n it requires no more than n * k1 k0 space. k, k0, k1 are constants.

CodePudding user response：

For lists, the space complexity grows linearly as the number of elements increases. But the variable holds a reference to a list, and the reference is of fixed size, so changes in the actual list data will not cause a change in the reference size.

This relationship is like the data allocated on the heap and the corresponding pointer in c.