Time Complexities

worst; logn; logn; best; 1; 1

When removing from heaps, the ________ case is O(______). This is where, after removing the root, the last element is put at the root and must bubble down ________ levels. The ________ case is O(________). This is where we only have to downheap ______ level after swapping the last element to the root

worst; logn; logn; worst; n; best; 1

When adding to heaps, the _________ case is O(_________)*. This is when adding a new element, it bubbles up to the root through _________ levels. The _______ case (unamortized) is O(_____). This is where we have to resize and must copy all the data to a new larger array. The _______ case is O(______). This is where the newly added data belongs in the leaf and doesn’t have to bubble up

n; all; nlogn; n

When performing buildHeap, the run time is O(_____) for ______ cases. Without buildHeap, the runtime is O(______) because the elements would be added one by one (which is using add() for ____ elements)

logn; all

When removing from an AVL, the run time is O(_________) for _______ cases

logn; all

When adding to an AVL, the run time is O(__________) for _______ cases

logn; 1; root

When searching an AVL, the average and worst cases are O(____________). The best case is O(_____) because the target value is at the _______

1

The run time to calculate the height of an AVL is O(________)

n

When doing traversals on an AVL, the run time is always O(______)

1

When doing rotations on an AVL, the run time is always O(________)

logn; all

When adding to a 2-4 Tree, the runtime is O(_______) for ______ cases

logn; all

When removing from a 2-4 Tree, the runtime is O(________) for _____ cases

logn; 1; root

When removing from a 2-4 Tree, the average and worst cases are O(________), and the best case is O(______) because the element exists in the _______ of the tree

logn; all

When calculating the height of a 2-4 Tree, the runtime is O(________) for ____ cases