Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
58 Cards in this Set
- Front
- Back
|
Sorted Array search |
O(log2 n) |
|
|
Sorted Array select i-th largest element |
O(1) |
|
|
Sorted Array min/max |
O(1) |
|
|
Sorted Array predecessor/successor |
O(1) |
|
|
Sorted Array rank given key how many elements are smaller than key? |
O(log2 n) |
|
|
Sorted Array output in sorted order |
O(n) |
|
|
Sorted Array insert |
O(n) -- slow |
|
|
Sorted Array delete |
O(n) -- slow |
|
|
Balanced BST search |
O(log2 n) |
|
|
Balanced BST select, worst case |
O(log2 n) |
|
|
Balanced BST min/max |
O(log2 n) |
|
|
Balanced BST predecessor/successor |
O(log2 n) |
|
|
Balanced BST output in sorted order |
O(n) |
|
|
Balanced BST insert |
O(log2 n) |
|
|
Balanced BST delete |
O(log2 n) |
|
|
Generic BST search, worst case |
O(H) where Height = Nodes |
|
|
Generic BST delete-min |
O(log2 n) |
|
|
Linked List delete-min |
O(n) |
|
|
Linked List insert |
O(n) |
|
|
Heap delete-min |
O(log2 n) |
|
|
Heap Insert |
O(log2 n) |
|
|
Heap min/max |
O(log2 n) |
|
|
Balanced BST extract min/max |
O(log2 n) |
|
|
Sorted Array extract min/max |
O(n) |
|
|
Heap extract min/max |
O(log2 n) |
|
|
Treap insert |
O(H) |
|
|
Treap tree splitting |
O(H) |
|
|
Graph BFS/DFS traverse |
O(|V| + |E|) |
|
|
Dijkstra's Algorithm best runtime |
O(|E| log2 |V|) |
|
|
Dijkstra's Algorithm worst case |
O(|E| log2 |E|) |
|
|
Graph BFS/DFS check for cycles |
O(|V|) |
|
|
Union-Find check for cycles |
O(1) |
|
|
Kruskal's Algorithm check for cycles |
O(|V| |E|) |
|
|
Eager union leader pointer updates |
O(|V|) |
|
|
Smart union leader pointer updates |
O(log2 |V|) |
|
|
Eager and simple union union (single) |
O(n) |
|
|
Eager and simple union find (single) |
O(1) |
|
|
Eager and simple union N-1 unions and M finds |
O(n^2 + m) |
|
|
Eager and smart union union (single) |
O(log2 n) |
|
|
Eager and smart union find (single) |
O(1) |
|
|
Eager and smart union N-1 union and M finds |
O(n log2 n + m) |
|
|
Lazy and simple union union (single) |
O(1) |
|
|
Lazy and simple union find (single) |
O(n) |
|
|
Lazy and simple union N-1 unions and M finds |
O(n + mn) = O(mn) |
|
|
Lazy and smart union union (single) |
O(1) |
|
|
Lazy and smart union find (single) |
O(log2 n) |
|
|
Lazy and smart union N-1 unions and M finds |
O(n + m log2 n) |
|
|
Path-compression original find, worst case |
O(log2 n) |
|
|
Path-compression repeat find, worst case |
O(1) |
|
|
Linked List find |
O(n) |
|
|
Skip List find |
O(log2 n) |
|
|
Skip List min |
O(1) |
|
|
Skip List delete-min |
O(1) |
|
|
B-Tree find, worst case |
O(log2 n) |
|
|
Hash table find, average |
O(1) |
|
|
Hash table insert, average |
O(1) |
|
|
Hash table delete, average |
O(1) |
|
|
Hash table worst case performance |
O(n) |
