Big-O is about growth, not raw speed
Big-O notation describes how an algorithm's time or memory use grows as input size grows — it doesn't tell you an operation takes exactly 3 milliseconds, it tells you whether doubling your data roughly doubles the work (O(n)) or squares it (O(n²)). That distinction is what predicts whether code that works fine on 100 items will still work on a million.
Arrays: fast access, slow insertion in the middle
Arrays store elements contiguously in memory, which makes accessing any index O(1) — the address is just a calculation, not a search. Inserting or removing from the middle is O(n), since every following element has to shift over by one.
Hash maps: near-instant lookup by key
const cache = {}
cache['user_42'] = { name: 'Amara' }
cache['user_42'] // O(1) average lookupA hash map computes a numeric hash from the key to jump almost directly to where the value is stored, giving average O(1) lookup, insertion, and deletion — dramatically faster than scanning an array for a matching value, which is O(n).
Linked lists: cheap insertion, no random access
A linked list is a chain of nodes, each pointing to the next. Inserting at a known position is O(1) — just rewire two pointers — but there's no way to jump to "the 500th element" without walking the list from the start, making that O(n). In practice, arrays win for most use cases on modern hardware because of memory locality, and linked lists are less common in application code than textbooks suggest.
Trees: hierarchy and ordered search
50
/ \
30 70
/ \ / \
20 40 60 80A binary search tree keeps everything smaller than a node to its left, everything larger to its right — search, insert, and delete are all O(log n) on a balanced tree, because each comparison eliminates half the remaining possibilities. Self-balancing variants (AVL, red-black trees) guarantee this stays true even under adversarial insertion order.
Graphs: relationships, not hierarchy
A graph is nodes connected by edges, with no requirement for hierarchy — a social network, a road map, a dependency graph are all naturally graphs. Breadth-first search (BFS) finds the shortest path in an unweighted graph; depth-first search (DFS) explores as far as possible down one path before backtracking, useful for tasks like detecting cycles.
The actual skill isn't memorizing definitions. It's recognizing, given a real problem, which structure's tradeoffs fit: "I need fast lookups by ID" points to a hash map; "I need sorted order maintained as I insert" points to a balanced tree; "I need to model who's connected to whom" points to a graph.
Why this still matters beyond interviews
Choosing an array where a hash map belongs (or vice versa) is a common, invisible source of slow code — invisible because it works fine in testing with 50 records and only becomes a visible problem once real user data reaches tens of thousands of rows.
Comments