Exam 2 Cram

BST add()

Average and Best: O(log n)
Worst: O(n)

BST remove()

Average and Best: O(log n)
Worst: O(n)

BST search()

Average and Best: O(log n)
Worst: O(n)

BST height()

Average and Best: O(log n)
Worst: O(n)

Heap insert()

Always O(log n)

Heap remove():

Always O(log n)

Heap heapify()

O(log n) for the first element; O(n) for the full heap

Heap BuildHeap():

O(n) always

AVL add()

O(log n) always

AVL Remove()

O(log n) always

AVL search()

O(log n) always

AVL rotation() and height()

O(1) always

AVL traversal

O(n) always

2-4 Tree Add()

Always O(log n)

2-4 Tree Remove()

Always O(log n)

2-4 Tree search() and height() and promote()

O(log n) always for all three

HashMap put()

Best and Average: O(1)
Worst: O(n)

HashMap get()

Best and Average O(1):
Worst: O(n)

HashMap remove()

Best and Average O(1):
Worst: O(n)

HashMap (external chain is SLL):

add(): O(1) or O(n) depending on if you need to search a list for duplicates or just add at the head
remove(): O(1) if just one element in a bucket, O(n) if more
get(): O(1) if just one element, O(n) if more

HashMap (external chain is BST):

add(): O(log n), unless degen then O(n)
remove(): O(log n) if balanced; O(n) if unbalanced as height is linear
get(): O(log n) if balanced; O(n) if unbalanced as height is linear

HashMap (external chain is AVL):

O(log n) for all cases of add, remove, and get

SkipList

O(log n) always for add removal and search if its a fair coin
O(n) if its not