4
$\begingroup$

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.

$\endgroup$
4
  • 1
  • $\begingroup$ 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). $\endgroup$
    – GACy20
    Jan 4 at 15:07
  • 1
    $\begingroup$ 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. $\endgroup$
    – GACy20
    Jan 4 at 15:09
  • $\begingroup$ @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. $\endgroup$ Jan 4 at 20:38
6
$\begingroup$

I can't answer that question reliably, because it depends on the behavior of the memory allocator in Python, and I don't think we're provided any guarantees about that. The memory allocator might deallocate the space after the function returns, or it might deallocate in every iteration.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.