Time complexity of popping elements from list in Python!
If you are learning python after JavaScript as your first language. You will probably be socked by the inbuilt functions we have in python.
While removing any element from the list we should take care about the complexity and we have function pop() which pop the element from the list on provided index. Does it care about the time complexity?
Consider we have following list.
a = [1, 2, 3, 4, 5, 6]By doing a.pop() with no arguments it will remove and return the last element which has O(1) time complexity. Because it just remove the last element and do not need to re-arrange the elements.
Python list is implemented as an array of pointers. If we do a.pop(k)first remove and return the k'th and then moves all the elements after k one position up. So that we do not have null/empty/void value at k’th position.
So what will be the time complexity when we pass an argument? Consider the length of list is N and we need to remove an element at k position as follows.
a.pop(k)The general formula for this time complexity will be:
O(N-k)Worst case time complexity will be:
# when we have to remove the first element
O(N)# if we consider list we have above
a = [1, 2, 3, 4, 5, 6]
O(6-0) = O(6) = O(N)
Average case time complexity will be:
O(k) or O(N/2)As we have six elements in the list and removing middle element of the list is N-k which will have k operations. So simply we will have O(k) average time complexity.
Looking at the complexity, we should not use list to manage queue. Instead we have deque in python.
Happy coding till then!
