What are the fundamentals of calculating space complexity in loops?

Question

Imagine you loop n times, and every iteration you create a string of space n with scope only within that iteration (thus it is no longer accessible in the next iteration). I would look and say that I use O(n^2) space because for n iterations, I use n space.

However, logically, if every loop you destroy the previous iteration's string (of n space) and overwrite it with this iteration's string (of n space), throughout the entire loop, you would only be using O(n) space. I am confused about whether to confirm O(n) or O(n^2) space?

Take this example:

s = "hello"
for _ in range(len(s)):
    newString = s[:]
return newString

Answer 1

In theory, worst-case space usage is O(n^2) as you mentioned: n copies of n-length strings.

But in practice, it'll be lower due to implementation details like garbage collection (i.e. reference counting) and string interning (i.e. s[:] can return the same object as s). For example in CPython 3.8.12:

>>> s = 'hello'
>>> s is s[:]
True

Answer 2

You only measure the maximum amount of space that you need at any one time. Your loop requires O(n) space, because as you say, only one iteration is in scope at any one time.

In garbage-collected languages where you don't explicitly free memory, it's reasonable to trust the implementation of whatever language you're using to ensure that the amount of space you use in reality is at most proportional to the amount you need, so it doesn't affect your space complexity.

It's also reasonable to ignore issues like memory fragmentation for asymptotic space complexity analysis in most cases, even though problems like that can actually change the real-world asymptotic complexity.

Answer 3

Your question does not really have an answer, because dynamic allocation has an unknown cost, both in terms of time and of space !

Algorithm analysis usually assumes that an infinite memory space is available, in a way "globally allocated", and with constant access cost. This model has no concept of dynamic allocation.

You might invent a model that does integrate dynamic allocation, with well-selected time and space costs. If allocation is assumed "on the stack", constant time and O(n) space (counted just once as memory is released upon return) is reasonable. For "heap" allocation, you are in the mist.