My one-page Big-O cheat sheet for every structure we covered

My own summary, typed up from my notes. Average case unless noted. ArrayList: access O(1), add to back O(1) amortized, add to front O(n) Singly linked list (with tail): add to front/back O(1), remove from back O(n) Stack / Queue (array- or list-backed): push/pop/enqueue/dequeue O(1) BST: search/insert/remove O(log n) average, O(n) worst (degenerate tree) AVL tree: search/insert/remove O(log n) worst case, thanks to rebalancing Heap: add/remove O(log n), peek O(1), build from array O(n) Hash map: put/get/remove O(1) average, O(n) worst with bad collisions Sorts: Bubble / insertion / selection: O(n²) worst; insertion is O(n) on nearly sorted data Merge sort: O(n log n) always, stable, needs extra space Quick sort: O(n log n) average, O(n²) worst with bad pivots Heap sort: O(n log n), in place, not stable The trick that helped me: for every entry, be able to say which step dominates.