What are the fundamentals of calculating space complexity in loops?

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

I am primarily asking this question for the space of a DS + Algo interview.

• This is why algorithms are described using pseudocode. There are a bunch of hidden assumptions behind this, such as "there is no garbage collection, memory is deallocated explicitly/it is automatically deallocated once variables go out of scope" etc. You can easily have 2 implementations of a programming language where the same code shows $O(n^2)$ space complexity in one implementation and $O(n)$ in the other (e.g. have a Python implementation that does not collect any garbage, and an other one that uses refcounting and deallocated the old string right after newString is overridden). Jan 4 at 15:07
• However, in general, we always take the "least" complexity that would be feasible to implement. Most often to actually achieve that complexity in a real programming language you do have to complicate a bit the code because the "hidden details" will have to be explicitly implemented. Jan 4 at 15:09
• @GACy20: Indeed, that is exactly the case. Of the current mainstream implementations of Python, one is guaranteed to use Reference Counting with deterministic collection and finalization for non-cyclic data structures (with occasional mark-and-sweep tracing GC to collect cycles), while all others use quite sophisticated tracing GCs that – given enough memory – will probably never run for such a simply problem. Jan 4 at 20:38

What we can say is that it is possible to implement this algorithm using $$O(n)$$ space, and it is possible to implement it in a way that uses $$O(n^2)$$ space. If we were presented with an algorithm (not with code) and we cared about space, one might reasonably make the implicit assumption that you will implement it in a way that uses $$O(n)$$ space and thus describe the algorithm as having $$O(n)$$ space complexity.