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?
Understanding Data Structures Big-O and Operation Costs
Big O describes how the amount of work grows as the input becomes larger. It ignores fixed setup costs and small constant differences. This makes it useful for comparing designs at a large scale, but it does not predict the exact running time of one program on one computer.
A loop that visits every item has linear growth. A process that repeatedly cuts the remaining search range in half has logarithmic growth. Nested loops are not automatically quadratic.
Their total work depends on how many times each loop actually runs. Always identify the input size first. It might be the number of records, edges, characters, or requests.
Memory layout changes real performance even when two structures have similar Big O costs. Array elements are stored close together. Modern processors can often read nearby elements efficiently because of caching.
Linked nodes may be scattered across memory, so following links can be slower in practice. Dynamic arrays occasionally need a larger block of memory. During that resize, every existing element may be copied.
The average cost remains low across many appends because resizing happens rarely, yet one individual append can be expensive. This is the meaning of amortized analysis. It studies the total cost of a long sequence of operations rather than judging each operation alone.
Hash tables depend on a hash function that spreads keys across buckets. Equal keys must produce the same hash result, while different keys should usually spread out. Collisions are normal, not proof that a table is broken.
They are handled by storing several entries in one bucket or by probing for another location. Performance worsens when the table becomes too full, so implementations resize based on a load factor. Trees maintain order, which is valuable when a program needs the smallest item, a range of values, or sorted output.
Heaps are different from sorted lists. They guarantee that the highest or lowest priority item is easy to find, but they do not make every item fully ordered.
Graphs require careful counting because the number of connections can matter more than the number of vertices. A social network, road map, course prerequisite chart, and web link system can all be modeled as graphs. An adjacency list stores only connections that exist, so it is usually efficient for sparse graphs.
An adjacency matrix uses space for every possible pair of vertices, which can be useful when connection checks must be extremely fast. When studying operation costs, write down what information is already known. Deleting a linked node is cheap only after reaching it.
Updating a heap is cheap only when its position can be found. Practice tracing small examples, then state the work done per item and the number of items affected. This prevents memorized tables from hiding the reason behind each cost.