Do I need to memorise every row here?

Know the array, hash table, and balanced tree rows cold — they come up constantly. Graph algorithm complexities matter more for roles that specifically test graph problems.

Why is build-heap O(n) and not O(n log n)?

A tighter analysis of heapify shows most nodes are near the bottom of the tree and need very few swaps, so the sum across all nodes works out to linear, not the naive n × log n upper bound.

Which sort should I default to if asked to "just sort this"?

Say merge sort or heapsort if guaranteed O(n log n) matters, or mention that most languages’ built-in sort (often Timsort or introsort) already handles this well in practice.

Data structure and algorithm complexity cheat sheet

The number that matters on a whiteboard is rarely the algorithm name — it is whether you can state its time and space complexity correctly and defend it under a follow-up question.

This is a lookup table, not a tutorial: array and hash table operations, the sorting algorithms actually worth knowing cold, and the handful of rules — amortized cost, recursion stack space — that catch people out.

Data structure operations (average case)

Array: Access O(1), search O(n), insert/delete in the middle O(n) due to shifting. A dynamic array’s append at the end is O(1) amortized.
Singly linked list: Access and search O(n), since you must walk from the head. Insert or delete at a known node, or at the head, is O(1) once you are there.
Stack / queue: Push, pop, enqueue and dequeue are all O(1), whether array- or linked-list-backed, because only the ends are ever touched.
Hash table: Average access, search, insert and delete are O(1). Worst case is O(n) if many keys collide into the same bucket.
Balanced binary search tree (e.g. red-black tree): Access, search, insert and delete are O(log n) in both the average and worst case, because the tree stays height-balanced.
Binary heap: Find-min or find-max is O(1). Insert and extract-min/max are O(log n). Building a heap from an unsorted array is O(n), not O(n log n) — a common trap.
Trie: Insert and search are O(k), where k is the key length, independent of how many keys are stored.

Sorting algorithms

Bubble / insertion / selection sort: O(n²) average and worst case, O(1) extra space. Insertion sort drops to O(n) best case on nearly sorted data.
Merge sort: O(n log n) in every case, O(n) extra space, and stable — equal elements keep their relative order.
Quicksort: O(n log n) average, O(n²) worst case on already-sorted input with a naive pivot choice, O(log n) space for the call stack. Not stable.
Heapsort: O(n log n) in every case, O(1) extra space, but not stable.
Counting / radix / bucket sort: O(n + k), where k is the range of input values. Only faster than comparison sorts when k is not much larger than n.
Timsort (Python’s sort, Java’s Arrays.sort for objects): A hybrid of merge sort and insertion sort: O(n log n) worst case, O(n) best case on already-sorted runs, and stable.

Graph traversal

Breadth-first search (BFS): O(V + E). Finds the shortest path by edge count in an unweighted graph.
Depth-first search (DFS): O(V + E). Used for cycle detection, topological sort and finding connected components.
Dijkstra’s algorithm: O((V + E) log V) with a binary heap. Shortest path with non-negative edge weights only.
Bellman-Ford: O(V × E). Handles negative weights and detects negative cycles, but is slower than Dijkstra.

Rules that trip people up

O(n) vs O(2n): Big-O drops constants, so O(2n) is just O(n). An interviewer testing this wants to hear "still linear," not a calculation of the coefficient.
Amortized vs worst case: A dynamic array’s append is O(1) amortized because occasional resizes cost O(n) but happen rarely enough to average out. The worst case for a single call is still O(n).
Recursion and the call stack: A recursive solution with depth n uses O(n) space even with no extra data structure allocated — people forget to mention this when asked for space complexity.
Converting recursion to iteration: Rewriting a recursive solution with an explicit loop and your own stack structure can drop O(n) auxiliary call-stack space to O(1), a common follow-up question.

How this is worked out

Grouped into data structures, sorting, graph traversal, and the rules interviewers use to catch a shallow answer.
Complexities are stated for the standard implementation of each structure — a specific language’s library type can differ slightly.
Space complexity is called out wherever it is easy to forget, since interviewers ask for it as a follow-up more often than they ask upfront.

What this does not cover

This is a reference table, not a algorithm-writing tutorial — it assumes you already know roughly how each structure or algorithm works.
Best, average and worst case are only distinguished where they actually differ meaningfully; otherwise one figure is given.
Language-specific library complexities (e.g., a specific hash map implementation’s exact worst case) can vary — verify against the language you are interviewing in if it matters.

Questions people ask

Do I need to memorise every row here?: Know the array, hash table, and balanced tree rows cold — they come up constantly. Graph algorithm complexities matter more for roles that specifically test graph problems.
Why is build-heap O(n) and not O(n log n)?: A tighter analysis of heapify shows most nodes are near the bottom of the tree and need very few swaps, so the sum across all nodes works out to linear, not the naive n × log n upper bound.
Which sort should I default to if asked to "just sort this"?: Say merge sort or heapsort if guaranteed O(n log n) matters, or mention that most languages’ built-in sort (often Timsort or introsort) already handles this well in practice.

Where these figures come from

Rates and rules on this page were last checked against the source on 31 August 2026. Tax law changes; check the source before you rely on a number for a decision.

Related calculators

Running these numbers because you are weighing a move? See what is open right now.