Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

In Python, a list has list.insert(i, x) to "Insert an item at a given position.". In C++, there is a list as well. In C++, cost/complexity of inserting an element anywhere is O(1). Is it the same for a Python list? If not, can anything else be use to get O(1) insert time in Python?

like image 863
user3654650 Avatar asked Nov 22 '14 03:11

user3654650


People also ask

What is the time complexity of list insert?

Python List insert() Time Complexity. The time complexity to insert an element at a given index is O(n). This means that the complexity increases linearly with the number of elements in the list.

What would be the time complexity of insert and delete?

If you don't know the location, then you need to traverse the list to the location of deletion/insertion, which takes O(n) time. ** The deletion cost is O(log n) for the minimum or maximum, O(n) for an arbitrary element. There is some confusion in deletion in array.

Can we perform insertion in O 1 time complexity?

Worst time complexity for inserting into list is O(n-i) , where n is the length of the list and i is the index at which you are inserting. So in case if you are inserting at the last index, that makes it O(1) .

What is runtime complexity of the list's built in append () method?

Time Complexity: Append has constant time complexity i.e.,O(1). Extend has a time complexity of O(k). Where k is the length of the list which need to be added.


1 Answers

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

like image 153
Tanveer Alam Avatar answered Oct 07 '22 23:10

Tanveer Alam