In-place, strictly In-place, and O(1) space algorithms

How does one categorize an algorithm like this:

def foo(arr):
    # original_len = len(arr)
    tmp = []
    while arr:
        tmp.append(arr.pop())
    while tmp:
        arr.append(tmp.pop())

The definitions get kinda of confusing because theoretically, at any point len(arr) + len(tmp) ~= original_len, so I am not using extra memory outside the extra list object which is constant. But here are some of my thoughts:

I do actually need extra memory, as if I only had 32 buckets of memory laid out sequentially, if the original array requires 32 buckets, then when I put the 31st bucket into the new list after putting the 32nd, I will need a 33rd bucket while the 31st bucket would remain empty
It is definitely in-place as it literally alters the data in-place, but perhaps not strictly in-place, if that distinction exists
Perhaps the fact that I am just allocating a new list already rules out it being strictly in-place, but if I had more control over the memory, one could imagine building the second list as one that grows toward lower memory addresses, thus reutilizing the same space, would that then not be strictly in-place?
Dynamic lists don't actually work that way anyway, since they allocate continuous blocks of memory, so the above is irrelevant

My issue is that I have seen some claim (perhaps incorrectly) that snippets similar to that one are O(1) in space, and I also, generally when doing these broad stroke "analysis", some implementation details are ignored.

Solution

We can ignore the fact that your function doesn't actually have a result, doesn't really achieve anything (because it reverses a list twice), and has side effects during execution (arr is slowly exhausted and then reconstructed). We can still analyse it.

A function is in-place if it only uses a fixed amount of additional space (auxiliary space) to perform an algorithm and the input is transformed where it resides.

A function is strict in-place if it is in-place and it also does not implicitly uses more space, through recursion or implicit stack growth (like you would get from chaining generators).

A function is in O(1) if it uses a fixed amount of space, even if the space needed does not stay in one place. A function can be in O(1) when it's not in-place.

Your function is none of the above. The larger arr is, the more space it needs to allocate for tmp. You're correct that arr decreases in size as tmp increases, but that doesn't change the fact that you're not explicitly reusing the space arr was occupying. Instead, your function allocates new space for the elements of tmp.

It's not in-place as all the data leaves arr before returning (if it does return, it may be reallocated elsewhere), and thus it is definitely not stricty in-place. And it's not in O(1), since you need more auxiliary space for larger inputs.

You'd have to provide some of these "similar snippets" for us to comment on why those are in O(1).

By the way, this is a strict in-place function in O(1) that does the same as yours:

def bar(arr):
    for i in range(len(arr) // 2):
        arr[i], arr[-i-1] = arr[-i-1], arr[i]
    for i in range(len(arr) // 2):
        arr[i], arr[-i-1] = arr[-i-1], arr[i]

You could print tmp halfway through foo(arr) and arr halfway through bar(arr) and see they are the same.

This is in-place because it does all the work where arr resides, never reallocating arr. It is strict in place because it does so without implicit stack growth. And it is in O(1) because the amount of memory needed to perform its function is fixed (the range() doesn't take up more space for larger arr).

You could make it non-strict in place:

def baz(arr, i = 0):
    arr[i], arr[-i - 1] = arr[-i - 1], arr[i]
    if i < len(arr) // 2:
        baz(arr, i + 1)
    arr[i], arr[-i - 1] = arr[-i - 1], arr[i]

This is no longer strict in-place, since it needs more recursion for larger arr, even though there is no auxiliary space explicitly allocated and it is still in-place. Whether this is considered in O(1) depends on whether stack space is considered. I would consider it not to be in O(1), but under some definitions it may be.