time complexity

mergesort runtime

o(n log n)

insert item into BST

o(height of root node)

check if BST contains an item

o(height of root node)

remove item from BST

o(height of root node)

AVL insert

o(log n)

AVL remove

o(log n)

AVL contains

o(log n)

AVL find

o(log n)

linked list enqueue

o(1)

sorted linked list enqueue

o(n)

multiple queues(k priority) enqueue

o(1)

balanced BST enqueue

θ(log n)

linked list dequeue

o(n)

sorted linked list dequeue

o(1)

multiple queues (k priority) dequeue

o(k)

balanced BST dequeue

θ(log n)

linked list size

o(1)

sorted linked list size

o(1)

multiple queues (k priority) size

o(k)

balanced BST size

o(1)

worst case removing smallest item from a heap w/ size n

o(log n)

linked list peek

o(n)

sorted linked list peek

o(1)

multiple queues (k priorities) peek

o(k)

balanced BST peek

θ(log n)

heap enqueue worst time complexity

o(log n)

heap enqueue average time complexity

o(1)

heap dequeue

o(log n)

heap peek

o(1)

heap size

o(1)

heap remove minimum item

o(n log n)

unsorted list contains

o(n)

sorted list contains

o(log n)

queue contains

o(n)

stack contains

o(n)

tree contains

o(n)

balanced BST contains

o(log n)

heap contains

o(n)

adding item to a hashtable w/ chaining worst time complexity

o(n)

adding item to a hashtable w/ chaining average time complexity

o(1)

adding items to a hashtable w/ linear probing worst time complexity

o(n)

adding items to a hashtable w/ linear probing average time complexity

o(1)

BFS

o(V+E)