What is the cost/ complexity of insert in list at some location?

by

list

The Average Case assumes parameters generated uniformly at random.

Internally, a list is represented as an array; the largest costs come from growing beyond the current allocation size (because everything must move), or from inserting or deleting somewhere near the beginning (because everything after that must move). If you need to add/remove at both ends, consider using a collections.deque instead.

enter image description here

So inserting an element at given position will always have the time complexity of O(n) as both insert method and slicing has time complexity of O(n) and O(k).
Only append which inserts at the end of list have O(1) time complexity.
From Python Wiki

Lists:
                               Complexity
Operation     | Example      | Class         | Notes
--------------+--------------+---------------+-------------------------------
Index         | l[i]         | O(1)          |
Store         | l[i] = 0     | O(1)          |
Length        | len(l)       | O(1)          |
Append        | l.append(5)  | O(1)          |
Clear         | l.clear()    | O(1)          | similar to l = []

Slice         | l[a:b]       | O(b-a)        | l[1:5]:O(l)/l[:]:O(len(l)-0)=O(N)
Extend        | l.extend(...)| O(len(...))   | depends only on len of extension
Construction  | list(...)    | len(...)      | depends on lenghth of argument

check ==, !=  | l1 == l2     | O(N)          |
Insert        | l[a:b] = ... | O(N)          |
Delete        | del l[i]     | O(N)          | 
Remove        | l.remove(...)| O(N)          | 
Containment   | x in/not in l| O(N)          | searches list
Copy          | l.copy()     | O(N)          | Same as l[:] which is O(N)
Pop           | l.pop(...)   | O(N)          |
Pop           | l.pop()      | O(1)          | same as l.pop(-1), popping at end
Extreme value | min(l)/max(l)| O(N)          |
Reverse       | l.reverse()  | O(N)          |
Iteration     | for v in l:  | O(N)          |

Sort          | l.sort()     | O(N Log N)    | key/reverse doesn't change this
Multiply      | k*l          | O(k N)        | 5*l is O(N): len(l)*l is O(N**2)

From here

More Related Contents:

  1. What is time complexity of a list to set conversion?
  2. Sliding window maximum in O(n) time
  3. What is the time complexity of Python List Reverse?
  4. How to make a dict from n’th indices of tuples in list
  5. Why does this code for initializing a list of lists apparently link the lists together? [duplicate]
  6. Access multiple elements of list knowing their index
  7. Appending the same string to a list of strings in Python
  8. Python list doesn’t reflect variable change
  9. Removing item from list causes the list to become NoneType
  10. Why is [] faster than list()?
  11. How can I multiply all items in a list together with Python?
  12. How to unzip a list of tuples into individual lists? [duplicate]
  13. Remove trailing newline from the elements of a string list
  14. Getting only element from a single-element list in Python?
  15. How to loop through all but the last item of a list?
  16. Writing a list to a file with Python, with newlines
  17. How can I convert each item in the list to string, for the purpose of joining them? [duplicate]
  18. How can I initialize a dictionary of distinct empty lists in Python?
  19. Extract elements of list at odd positions
  20. How to read an array of integers from single line of input in python3
  21. Replace special characters in a string in Python
  22. List with duplicated values and suffix
  23. How to group elements in python by n elements [duplicate]
  24. Unexpected IndexError while removing list items [duplicate]
  25. How do I reverse a list or loop over it backwards?
  26. How to remove item from a python list in a loop? [duplicate]
  27. How to split an iterable into two lists with alternating elements
  28. How do I sort a list of objects based on an attribute of the objects?
  29. How can I match up permutations of a long list with a shorter list (according to the length of the shorter list)? [duplicate]
  30. Creating a list in Python with multiple copies of a given object in a single line

Leave a Comment