What you'll learn
Quick Answer
Array access is O(1) and search is O(n). Hash tables give O(1) average lookup, insert and delete, with O(n) worst case. Balanced trees give O(log n) for all three and keep order. Sorting is O(n log n) for comparison-based algorithms. The input constraints tell you the complexity you need: up to 10^7 allows O(n), up to 10^5 allows O(n log n), and only up to a few thousand allows O(n squared).
Data Structure Operations
Average case, with worst case noted where it differs meaningfully.
STRUCTURE ACCESS SEARCH INSERT DELETE SPACE
Array O(1) O(n) O(n) O(n) O(n)
Dynamic array O(1) O(n) O(1)* O(n) O(n)
Linked list O(n) O(n) O(1)† O(1)† O(n)
Stack O(n) O(n) O(1) O(1) O(n)
Queue O(n) O(n) O(1) O(1) O(n)
Hash table -- O(1)‡ O(1)‡ O(1)‡ O(n)
Binary search tree O(log n) O(log n) O(log n) O(log n) O(n)
(unbalanced) O(n) O(n) O(n) O(n)
Balanced BST O(log n) O(log n) O(log n) O(log n) O(n)
Heap O(1)§ O(n) O(log n) O(log n) O(n)
Trie -- O(m) O(m) O(m) O(n·m)
* amortised — occasionally O(n) when it resizes and copies
† only if you already hold the node; finding it is O(n)
‡ worst case O(n) when every key collides
§ O(1) to peek the min or max, O(log n) to remove it
m = length of the key or wordThe three footnotes are where interview follow-ups live. Linked list insertion is only O(1) with the node in hand — with an index it is O(n), the same as an array. Hash tables are O(1) on average. And dynamic array append is amortised O(1), meaning individual appends occasionally cost O(n) when capacity doubles.
Sorting and Searching
ALGORITHM BEST AVERAGE WORST SPACE STABLE
Bubble sort O(n) O(n²) O(n²) O(1) yes
Selection sort O(n²) O(n²) O(n²) O(1) no
Insertion sort O(n) O(n²) O(n²) O(1) yes
Merge sort O(n log n) O(n log n) O(n log n) O(n) yes
Quicksort O(n log n) O(n log n) O(n²) O(log n) no
Heapsort O(n log n) O(n log n) O(n log n) O(1) no
Counting sort O(n + k) O(n + k) O(n + k) O(k) yes
Radix sort O(nk) O(nk) O(nk) O(n + k) yes
SEARCH
Linear search O(1) O(n) O(n) O(1)
Binary search O(1) O(log n) O(log n) O(1) — requires sorted inputPoints interviewers probe:
- Quicksort's O(n²) worst case happens with consistently bad pivots — classically, naive quicksort on already-sorted data. Randomised pivots make it vanishingly rare.
- Insertion sort is O(n) on nearly-sorted data, which is why real library sorts switch to it for small chunks.
- Counting and radix sort beat O(n log n) because they do not compare elements — but they need bounded integer keys.
- Stability matters when sorting by one field after another. Merge and insertion sort are stable; quicksort and heapsort are not.
Built-in sorts: Python and Java objects use Timsort (stable, O(n) on sorted input), C++ std::sort uses introsort (quicksort that falls back to heapsort).
Graph Algorithms and Common Patterns
GRAPH ALGORITHM TIME SPACE
BFS / DFS O(V + E) O(V)
Dijkstra (binary heap) O((V+E) log V) O(V)
Bellman-Ford O(V·E) O(V) — handles negative weights
Floyd-Warshall O(V³) O(V²) — all pairs
Topological sort O(V + E) O(V)
Union-Find (with optimisations) ~O(1) amortised O(V)
COMMON PATTERNS TIME SPACE
Two pointers O(n) O(1)
Sliding window O(n) O(1) or O(k)
Binary search on answer O(n log n) O(1)
Prefix sums O(n) build, O(1) query O(n)
Backtracking (subsets) O(2ⁿ) O(n)
Backtracking (permutations) O(n!) O(n)
DP (1D) O(n) O(n) or O(1)
DP (2D) O(n·m) O(n·m) or O(m)Two things worth remembering. Recursion costs O(depth) space for the call stack even when it allocates nothing — which is why deep recursion overflows while the equivalent loop does not. And many DP solutions can drop to O(1) or O(m) space by keeping only the previous row instead of the full table, a common follow-up once you produce a working answer.
Reading the Constraints to Choose an Approach
This table is the most practically useful thing here. Competitive judges and interviewers usually give the input size, and it tells you which complexity is acceptable.
INPUT SIZE (n) REQUIRED COMPLEXITY TYPICAL APPROACH
n ≤ 10 O(n!) or O(2ⁿ) fine permutations, brute force
n ≤ 20 O(2ⁿ) subsets, bitmask DP
n ≤ 100 O(n³) Floyd-Warshall, 3 nested loops
n ≤ 1,000 O(n²) nested loops, simple DP
n ≤ 100,000 O(n log n) sorting, heaps, binary search
n ≤ 1,000,000 O(n) or O(n log n) hash maps, two pointers, prefix sums
n > 10,000,000 O(n) or O(log n) single pass, or mathsWork backwards from this. If n can be 100,000 and your idea is O(n²), it will time out — so stop coding and think of a better approach rather than optimising the constant factor.
A rough rule for the underlying arithmetic: most judges allow around 10^8 simple operations per second. O(n²) with n = 100,000 is 10^10 operations, which is roughly a hundred times too slow.
Say this reasoning out loud in an interview. "The constraint is 10^5, so I need at least O(n log n), which rules out the nested-loop approach" demonstrates exactly the thinking the question is testing — often more convincingly than the final code.
Working Out Complexity Quickly
You do not need formal maths. These heuristics cover nearly everything you will meet.
- No loop over the input — O(1).
- One loop — O(n). Two sequential loops are still O(n), since constants are dropped.
- Nested loops over the same input — O(n²). Over different inputs — O(n·m).
- A loop that halves or doubles — O(log n). Look for
mid = (low + high) / 2ori *= 2. - A loop containing a sort or a binary search — multiply: O(n log n).
- Recursion: multiply the number of calls by the work per call. Two calls on half the input with linear merging is O(n log n).
The three most common analysis mistakes:
Forgetting that a built-in sort costs O(n log n). Writing arr.sort() looks like one line but dominates an otherwise linear solution.
Forgetting that string concatenation in a loop is O(n²) in many languages, because each concatenation copies the whole string. Build a list and join once instead.
Forgetting the space cost of recursion, or of the hash map you added to make the time complexity better. Interviewers almost always ask for both, and the time-space trade is usually the point of the question.