1

Consider the following bubble sort program:

arr = map(int, raw_input().split(' '))
print "Unsorted: \n{arr_name}".format(arr_name = arr)

for j in range(len(arr) - 1, 0, -1):
    for i in range(j):
        if (arr[i] > arr[i + 1]):
            arr[i], arr[i + 1] = arr[i +1], arr[i]

print "Sorted: \n{arr_name}".format(arr_name = arr)

Usually a temp variable is used for sorting and that would be mean a space complexity of 0(1). But my understanding is that, tuple swap is only a reassignment of identifiers to objects (link). Does this require any additional space? What would be the space complexity here? Is it still O(1) because a tuple is created?

skr
  • 914
  • 3
  • 18
  • 35
  • Possible duplicate of [Fastest way to swap elements in Python list](https://stackoverflow.com/questions/4554130/fastest-way-to-swap-elements-in-python-list) – vishes_shell Jun 09 '17 at 16:29
  • Are you asking if the tuple swap takes a small, constant amount of memory *in the sorting operation*? – juanpa.arrivillaga Jun 09 '17 at 16:31
  • Yes. Normally, the `temp` variable used in swapping is the reason for specifying `O(1)`, because it is the additional memory used. I trying to find the counterpart of `temp` here. – skr Jun 09 '17 at 16:33

1 Answers1

4

Actually the swap gets optimized (in CPython, at least) so that no tuple is created:

>>> def f():
...     a,b = b,a
... 
>>> dis(f)
  2           0 LOAD_FAST                0 (b)
              3 LOAD_FAST                1 (a)
              6 ROT_TWO             
              7 STORE_FAST               1 (a)
             10 STORE_FAST               0 (b)
             13 LOAD_CONST               0 (None)
             16 RETURN_VALUE

It is still O(1), yes. Even if a tuple were created, it would still be O(1) since the tuple can be released immediately after the swap is performed.

The only extra memory being used is the stack space for holding the values to be swapped (which may not even be anything extra, since the maximum stack depth without the swap will probably already be enough). Then, the ROT_TWO opcode performs the swap:

    TARGET(ROT_TWO) {
        PyObject *top = TOP();
        PyObject *second = SECOND();
        SET_TOP(second);
        SET_SECOND(top);
        FAST_DISPATCH();
    }

Notice that no additional memory needs to be used; the top two stack elements are simply swapped. top and second above act as temporary variables.

arshajii
  • 127,459
  • 24
  • 238
  • 287
  • If no tuple is created, is there any additional memory usage to keep it `O(1)`. I understand that even then there will be some memory usage, but do we specify it as `O(1)`? How to justify that? – skr Jun 09 '17 at 16:35
  • I know it will not be more complex than `O(1)`. I am trying to figure out what memory exactly defines or makes up the `O(1)` in this case. – skr Jun 09 '17 at 16:38
  • @skr_robo I added some more details. The `ROT_TWO` opcode is what actually performs the swap. No additional memory needs to be allocated. – arshajii Jun 09 '17 at 16:39
  • Since no additional memory is used, why do we say `O(1)`. Is it because, by definition, this is the best complexity? – skr Jun 09 '17 at 16:42
  • @arshaaji I saw the `top` and `second` part now. I believe they can be considered to correspond to `O(1)`. – skr Jun 09 '17 at 16:44
  • @skr_robo Whatever additional memory that is being used (e.g. possibly extra stack space) is independent of the size of the input (i.e. the length of the list), which is what makes it O(1) rather than, say, O(n), where n denotes the length of the list. – arshajii Jun 09 '17 at 16:44
  • 1
    Okay. Got it. Thank you for the patient and clear explanation. – skr Jun 09 '17 at 16:45