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