Data Structures

||Append|Insert|Index|Find| |-|-|-|-|-| |[]|O(1)|O(1)|O(1)|| |{}|O(1)|O(1)|O(1)|| |Set()|O(1)|O(1)|O(1)|| |dequeue|O(1)|X|X|X|

• popleft O(1), double linked list, index O(1)

Dynamic array n times resize: 1+2+4+..+n=O(n)

	Time	Space
Tree	O(n*k), n is number of node k is per node operation	O(log n) best, O(n) worst

Operations

||| |-|-| |Binary search|O(log n)| |Sort|O(n log n)| |Min/Max|O(n)|