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

CodePudding user response：

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.

CodePudding user response：

Worst-case 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 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