Space Complexity of Python List Slices [duplicate]

Question

I'm having difficulty understanding the Space Complexity of Python List Slices.

For something like

arr[2:] = arr[2:][::-1]

is new space being allocated for the slice (like done in Strings since they are immutable) or is the operation done on the same array?

For something like:

ans = [i+1 for i in range(n)]

for i in range(k):
    ans[i:] = ans[i:][::-1]

What will be the space complexity? Will it be different or same than when ans is a string, something like ans = '12345...n'?

Answer 1

Python is strict about adhering to possible side effects. As far as the language is concerned, it is incorrect to perform any of your operations inplace.

Your operation

 arr[2:] = arr[2:][::-1]

are three separate slice operations:

• arr[2:] creates a new list from all elements (but the first two) of arr.
• ...[::-1] creates a new, reversed list from all elements of ....
• arr[2:] = ... replaces all elements (but the first two) of arr with ....

Each slice operation basically amounts to a primitive O(n) copy operation. Since only references are copied, the size or type of elements does not matter.

In your complete example, that amounts to three O(n) slice operations in an O(k) loop:

ans = [i+1 for i in range(n)]   # O(n)
for i in range(k):              # O(k)
    ans[i:] = ans[i:][::-1]     # O(n)

In total, the time complexity amounts to O(nk). Space complexity is only O(n), since the temporary slices are reclaimable immediately. You basically end up with the initial list, plus some temporary copies.

---

Will it be different or same than when ans is a string, something like ans = '12345...n'?

The complexity of the operations does not change - they are still the same primitive operations.

Practically, the CPython implementation cheats with certain objects. For example, += is inplace mutation for strings with refcount 1 even though strings are immutable. However, this does not apply to your slice usage.

In general, relying on inbuilt optimisations is a bad idea with Python.

---

If you are worried about space, start with writing lean code. For example, ans[i:][::-1] should simply be ans[i::-1]. That alone halves the temporary space required.