runtimes Flashcards
1
Q
BST min and max height
A
min: lower of log base 2 of N
max: N-1
2
Q
perfect BST height
A
lower of log base 2 of N
3
Q
BST search: best and worst
A
best: O(logN)
worst: (lower of logN) + 1
4
Q
BST insert: best and worst
A
best: O(logN)
worst: O(N)
5
Q
BST remove: best and worst
A
best: O(logN)
worst: O(N)
6
Q
enqueue
A
O(logN)
7
Q
dequeue
A
O(logN)
8
Q
peek
A
O(1)
9
Q
isEmpty
A
O(1)
10
Q
getLength
A
O(1)
11
Q
what is the complexity of removing a root node in a max heap
A
O(logN)
12
Q
heap insert and delete
A
O(logN) because height of heap is O(logN)
