Time complexity of swapping elements in a python list

Question

What is the Time complexity of swapping elements in a python list if I do the following

Case1: (Idiomatic way) Swaping two elements in a list

>>> a = [1, 2, 3, 4, 5]
>>> a[1], a[3] = a[3], a[1]  # Pythonic Swap --> x, y = y, x

>>> print(a)
[1, 4, 3, 2, 5]

Question1: What is the time complexity of the swap step? And what does python internally do.

Case2: (Very Inefficient way) Swaping two elements in a list

>>> a = [1, 2, 3, 4, 5]
>>> temp1, temp2 = a[1], a[3]
>>> del a[1]  # a = [1, 3, 4, 5]
>>> a.insert(1, temp2)  # a = [1, 4, 3, 4, 5]
>>> del a[3]  # a = [1, 4, 3, 5]
>>> a.insert(3, temp1)  # a = [1, 4, 3, 2, 5]
>>> print(a)
[1, 4, 3, 2, 5]

If I do it this way, Whenever I insert or delete at any index all the memory addresses present right to that index need to be moved/copied one step right or left respectively. So it takes O(K) where K is the number of addresses present right to the index where we inserted or deleted. Correct me if I am wrong.

---

Some Profiling

If the list is very small the run time complexity doesn't matter much which ever approach (Case1 or Case2) I use. But what if the list is very big like a = [i for i in range(0,1000000)] then what is the efficient way to swap two elements in a list. Here I did some basic profiling on the above two cases with a million record list swapping index 100 and 54321 and here is the result. Surprisingly both cases have almost the same performance.

a = [i for i in range(0,1000000)]

Case1 Profiling

$ time python3 case1_script.py

real    0m0.129s
user    0m0.088s
sys     0m0.041s

$ python3 -m cProfile case1_script.py

3 function calls in 0.060 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    1    0.047    0.047    0.060    0.060 list_ele_swap_profile.py:1(<module>)
    1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
    1    0.013    0.013    0.013    0.013 {range}

Case2 Profiling

$ time python3 case2_script.py

real    0m0.132s
user    0m0.090s
sys     0m0.042s

$ python3 -m cProfile case2_script.py

5 function calls in 0.115 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1    0.048    0.048    0.115    0.115 list_ele_swap_profile.py:1(<module>)
     1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
     2    0.001    0.001    0.001    0.001 {method 'insert' of 'list' objects}
     1    0.066    0.066    0.066    0.066 {range}

Question2: what is the efficient way to swap two elements in a list if the list is very big like above.

Question3: While thinking about this problem I have one more doubt, So if the deletion of an arbitrary element (let say middle index element) from the list requires copying/moving of the memory addresses then how is the deletion of an element from the list is O(1).

---

PS: I don't think this is a duplicate question, I have gone through the following questions but none of them have what I am looking for. I am interested in knowing the time/space complexity for the above operations. Thanks.

• Fastest way to swap elements in Python list
• Swapping elements in lists in python
• Swapping numbers in lists
• How does swapping of members in the python tuples (a,b)=(b,a) work internally?
• Is there a standardized method to swap two variables in Python?

Answer 1

The answer depends on your implementation of python. I'm assuming you are interested in the default CPython implementation. From now one, i say "python" instead of "cpython".

A list in python is more or less for your purpose like an array in C.

deleting an element in it requires shifting all elements above it, and the same goes for insertion, so that these two operations are O(i) where i is the number of items after the item you deleted/inserted. Your first answer is O(1), so way better.

Your profiling was wrong, because this size of array is actually quite small, and your timing also takes into account the time to build the array. Try the following experiment: build an array of size 100000 once, and try 100000 times to swap two elements in it. You will see that the first code is at least 100 times faster than the second one (that's the figures i obtained on my computer), and it is of course the good way to swap elements in a python list.

Answer 2

I think, it is O(1).This link Fastest way to swap elements in Python list shows the use of dis module. One of the assembly instruction in doing this is LOAD_FAST which is inserting elements onto stack. Insertion and deletion operations take O(1) in stack. The actual swapping instruction is ROT_TWO which is again swapping top elements of two stacks which is basically insertion and deletion, so I'm guessing this is also O(1).