CODEWITHSUNDEEP
pythonpython-3.xspace-complexity
green frog
green frog

Reputation: 166

Memory usage of an array of arrays referencing a single array?

Suppose in Python3 I have an array of size N and an array of N arrays.

a = []
b = []

for i in range(N):
  a.append(i)

for i in range(N):
  b.append(a)

Each b[i] now references the same array a. I think that this is still O(N) memory because when I access an array I am really accessing a reference to a block of memory so each b[i] holds constant space memory (the address to a) and the array a holds O(N) memory, so altogether this should be O(N) memory, rather than O(N^2) if each of the N^2 cells in b holds an independent value. Is this correct?

Upvotes: 1

Views: 316

Answers (2)

chepner
chepner

Reputation: 532093

Yes, it's O(N) for all practical purposes. a contains N references to int objects, and b contains N references to a. That's 2N references.

Technically, the amount of memory used by each int object referenced by a is a function of N, but because it's something like 24 + O(log_{2**32} N) bytes per int object, the hidden constant is so small that it only makes a difference when N is astronomically large (larger than any amount of memory you are likely able to afford or address).

On the other hand, the length of a list is also capped at sys.maxlen elements, which means in some sense that all lists use O(1) memory (with a very large constant). :)

Upvotes: 2

Mureinik
Mureinik

Reputation: 312056

Yes, this is correct. a's size is O(n), and b holds N references to the same instance of a. Overall, the memory complexity is O(n).

Upvotes: 2

Related Questions