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.
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
Answer from Tanveer Alam on Stack OverflowAssume I have a code:
arr1=array("i", [1, 2, 3, 4, 5])
I just wanted to ask what would be the time complexity for inserting an element at the end of the array by using the code:
arr1.insert(5,6)
output: array('i', [1, 2, 3, 4, 5, 6])
Although, I found online that Big O is O(1) but I don't get it. Initially my array was of fixed sized(5) and if I need to add a new element, I am essentially copying the old array [1,2,3,4,5] and pasting it in a new memory location with an empty space at the end so that I could add [6] in the end. This is my understanding, if this is right how is O(1) correct? shouldn't it be more?
Edit: It's O(n)
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.
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
The Python language doesn't specify the implementation of such operations, so different implementations may have different behavior. For CPython, the complexity of list.insert is O(n), as shown on this useful wiki page. I'm not aware of any list-like structure giving O(1) performance for inserting at an arbitrary index. (A dict gives O(1) insert performance in the average case, but is not ordered and does not enforce a contiguous sequence of indices.) The blist library provides an optimized list type that has an O(log n) insert.
list - Is a.insert(0,x) an o(n) function? Is a.append an O(1) function? Python - Stack Overflow
What is Python's list.append() method WORST Time ...
What is the Time complexity (Big O) for insertion of an element in the end of an Array?
What is Python's list.append() method WORST Time Complexity? It can't be O(1), right?
insert at the 0th index of a list requires shifting every other element along which makes it an O(N) operation. However, if you use a deque this operation is O(1).
append is an amortized O(1) operation since it simply requires adding the item on to the end of the list and no shifting is done. Sometimes the list needs to grow so it is not always an O(1) operation.
That is correct - insertion at the front of a Python standard list is O(n). Python lists are implemented as arrays, and thus inserting something at the front of the list requires shifting the entire contents over one spot. Appending, on the other hand, does not require any shifting, and thus is amortized O(1).
Note, however, that a.pop(i) is also an O(n) operation, because it requires shifting everything after the popped item over one spot. Thus, simply modifying your code to use append() instead of insert() would still not result in a linear algorithm.
A linear-time algorithm wouldn't use pop() but instead would do something like swap elements around so that the rest of the list doesn't have to be modified. For example, consider this:
def even_to_front(a_list):
next_even = 0
for idx in xrange(len(a_list)):
if not a_list[idx] % 2:
# a_list[idx] is even, so swap it towards the front
a_list[idx], a_list[next_even] = a_list[next_even], a_list[idx]
next_even += 1