1

Suppose we have the function below:

def foo(nums):
    nums = sorted(nums)
    return nums

In our function, we overwrite our original parameter nums, by storing the sorted version of the input in it.

My question is simple: does overwriting the input count toward auxiliary space occupation? More specifically, is the auxiliary space of our function O(N) or O(1)?

I know this question is not very nuanced, but I cannot find a clear answer anywhere. I understand that sorted() produces and stores a new version of the list. In this way, such an operation occupies O(N) space, where N is the length of the input list.

However, since we are overwriting the input, which already held a list of size N, do we still consider this operation occupying additional O(N) space?

Sebastian Wozny
  • 16,943
  • 7
  • 52
  • 69
LateGameLank
  • 113
  • 5

1 Answers1

2

However, since we are overwriting the input

This is not how Python works. We're not overriding the input. nums is a name for the input list within the function scope, and then we change it to be the name for the sorted list.

To better understand how Python names and values work I recommend this excellent PyCon talk.

Since the list behind nums is at least still referenced by the caller of the method, it can not be garbage collected until the operation finishes.

There will be a moment when the new list and the old list both co-exist, thus we take additional O(N) space.

Python uses Timsort for sorting which consumes O(N) space complexity, so even sorting it in place with .sort() still consumes O(N).

Sebastian Wozny
  • 16,943
  • 7
  • 52
  • 69