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. Continue reading...
