This cheat sheet summarizes the Big-O costs of common operations on core data structures used in college computer science. Students need it to compare design choices, predict performance, and prepare for coding interviews and exams. It focuses on access, search, insertion, deletion, traversal, and priority operations.
The goal is to help you choose a structure based on how the data will be used.
Key Facts
- Array access by index is O(1), but searching an unsorted array is O(n).
- Dynamic array append is amortized O(1), but inserting or deleting near the front is O(n) because elements must shift.
- Singly linked list insertion or deletion at a known node is O(1), but finding that node is O(n).
- Stack push, pop, and peek are O(1), and queue enqueue, dequeue, and front are O(1) when implemented with linked nodes or a circular buffer.
- Hash table search, insert, and delete are average O(1), but worst case O(n) when many keys collide or resizing is not handled well.
- Balanced binary search tree search, insert, and delete are O(log n), while an unbalanced tree can degrade to O(n).
- Binary heap find-min or find-max is O(1), while insert and extract-min or extract-max are O(log n).
- Graph traversal with adjacency lists is O(V + E), where V is the number of vertices and E is the number of edges.
Vocabulary
- Big-O notation
- A way to describe how an algorithm's running time or memory use grows as input size increases.
- Amortized time
- The average cost per operation over a sequence of operations, even if some individual operations are expensive.
- Hash collision
- A situation where two different keys map to the same location in a hash table.
- Balanced tree
- A tree that keeps its height near log n so search, insert, and delete remain efficient.
- Adjacency list
- A graph representation that stores, for each vertex, a list of its neighboring vertices.
- Priority queue
- An abstract data type that removes items according to priority rather than insertion order.
Common Mistakes to Avoid
- Calling dynamic array append O(1) without saying amortized is incomplete because occasional resizing takes O(n).
- Assuming hash tables are always O(1) is wrong because poor hashing, high load factor, or many collisions can make operations O(n).
- Treating linked list access as O(1) is wrong because reaching the kth element requires walking through nodes, which is O(k) and O(n) in general.
- Ignoring whether a tree is balanced leads to wrong costs because a balanced BST has O(log n) operations, but a skewed BST has O(n) operations.
- Confusing graph traversal costs with O(V) is wrong for adjacency lists because every edge may also be examined, so the cost is O(V + E).
Practice Questions
- 1 A dynamic array contains 1,000 elements. What is the Big-O cost of accessing element 750 by index, and what is the Big-O cost of inserting at index 0?
- 2 A graph has 80 vertices and 240 edges. What is the Big-O traversal cost using an adjacency list, and what expression represents the work in terms of V and E?
- 3 For a balanced binary search tree with n items, compare the Big-O costs of search, insert, and delete with the same operations in a sorted dynamic array.
- 4 A program frequently needs fast lookup by key, ordered iteration, and predictable worst-case performance. Should it use a hash table or a balanced tree, and why?