python’s Data Structures complexity analysis

Complexity Analysis of General Data Structures for Common Operations:

 

	Linked list	Array	Dynamic array	Balanced tree	Random access list
Indexing	Θ(n)	Θ(1)	Θ(1)	Θ(log n)	Θ(log n)
Insert/delete at beginning	Θ(1)	N/A	Θ(n)	Θ(log n)	Θ(1)
Insert/delete at end	Θ(1)	N/A	Θ(1) amortized	Θ(log n)	Θ(log n) updating
Insert/delete in middle	search time + Θ(1)[1]	N/A	Θ(n)	Θ(log n)	Θ(log n) updating
Wasted space (average)	Θ(n)	0	Θ(n)[2]	Θ(n)	Θ(n)

Complexity Analysis of Python’s Data Structures for Common Operations:

list

Internally, a list is represented as an array

Operation	Average Case	Amortized Worst Case
Copy	O(n)	O(n)
Append[1]	O(1)	O(1)
Insert	O(n)	O(n)
Get Item	O(1)	O(1)
Set Item	O(1)	O(1)
Delete Item	O(n)	O(n)
Iteration	O(n)	O(n)
Get Slice	O(k)	O(k)
Del Slice	O(n)	O(n)
Set Slice	O(k+n)	O(k+n)
Extend[1]	O(k)	O(k)
Sort	O(n log n)	O(n log n)
Multiply	O(nk)	O(nk)
x in s	O(n)
min(s), max(s)	O(n)
Get Length	O(1)	O(1)

collections.deque

A deque (double-ended queue) is represented internally as a doubly linked list

Operation	Average Case	Amortized Worst Case
Copy	O(n)	O(n)
append	O(1)	O(1)
appendleft	O(1)	O(1)
pop	O(1)	O(1)
popleft	O(1)	O(1)
extend	O(k)	O(k)
extendleft	O(k)	O(k)
rotate	O(k)	O(k)
remove	O(n)	O(n)

dict

 

Operation	Average Case	Amortized Worst Case
Copy[2]	O(n)	O(n)
Get Item	O(1)	O(n)
Set Item[1]	O(1)	O(n)
Delete Item	O(1)	O(n)
Iteration[2]	O(n)	O(n)

Reference:

http://wiki.python.org/moin/TimeComplexity

http://en.wikipedia.org/wiki/Linked_list

Advertisements

Creating a variable with value of another variable in Python

domain = "google"

vars()[domain] = 'Nextag'

print "Output is", google

Output

Output is NexTag