# What is space complexity of shrinking one array to increase another?

Say I have an array and I want to add those values to something else. What is the space complexity if I incrementally take one of those values off the first list and add it to the second? For example, I'm trying to convert a list to a string. I know that if I do the following, the space complexity will be O(N):

a = [1,2,3,4]
b = set(a)


But if instead I incrementally shrunk a, what would the space complexity be?

a = [1,2,3,4]
b = set()
for _ in range(len(a)):


Now b has what I want and a is empty. Does that make it O(1) in space complexity?

If the language matters, I'm most interested in Python, but I would like to know the most general answer as well.

• It all depends on what your model for space complexity is. Does the space used for the input count or not? What about the output? And, if neither counts, do you allow only sequential or also random access to either of those? These considerations make subtle differences not only for the space complexity of algorithms but also for theoretic models such as TMs (and related complexity-theoretic results). – dkaeae Feb 23 '19 at 17:39
• This seems to be a python-specific question, since it is only possible to answer it if we know the details of python implementation. – Yuval Filmus Feb 23 '19 at 17:56
• "Does that make in O(1) in space complexity?" So, do you mean the second algorithm will reuse the space freed by a.pop(), which is not obvious at all? – John L. Feb 23 '19 at 20:05
• I'm voting to close this question as off-topic because it depends on the implementation details of python. – Yuval Filmus Feb 24 '19 at 15:01

It is possible that the algorithm you describe runs in constant space. If the array a is stored earlier in memory than the string b, the system could, in principle, delete the last character of a, shuffle everything after it back one memory cell, then add a character onto the end of b, so no extra memory is used.
In reality, though, it's much more likely that the system doesn't keep moving things around and just allocates new memory each time a character is added to b, which is probably linear space. Except it could be worse. Maybe, every time you try to make b bigger, the system actually allocates completely new storage for the extended string, which could give quadratic space usage. Or maybe it's not that dumb and, each time you extend the string beyond its current memory allocation, it allocates a new chunk of memory that's double the size, so it can do lots of appends without reallocating memory every time. That would be linear, again.