Big O Cheat Sheet for Interviews (2026)

1. Array indexing by position — time complexity? Beginner

O(1). Direct memory offset. Same for reading and writing.

2. Array search for a value — time complexity? Beginner

O(n) unsorted, O(log n) if sorted (binary search).

3. Array insert at the end — time complexity? Beginner

O(1) amortized for dynamic arrays (Python list, Java ArrayList) — occasional O(n) resize. O(1) worst case only for fixed-size arrays with spare capacity.

4. Array insert at the beginning — time complexity? Beginner

O(n) — every element shifts right. Use a deque instead.

5. Linked list insert at head — time complexity? Beginner

O(1). Update two pointers, done.

6. Linked list search by value — time complexity? Beginner

O(n). No random access — must walk the chain.

7. Hashmap insert / lookup / delete — amortized? Beginner

O(1) average, O(n) worst case (all keys hash to same bucket). Java 8+ mitigates worst case with a red-black tree per bucket → O(log n) worst.

// Python dict, Java HashMap: O(1) average
d = {}
d['x'] = 1     # O(1)
v = d['x']     # O(1)
del d['x']     # O(1)

8. Binary search — time complexity? Beginner

O(log n). Requires sorted input. Common bug: mid = (lo + hi) // 2 in Java overflows for large lo+hi; use lo + (hi - lo) // 2.

9. Recursive Fibonacci without memoization — time complexity? Beginner

O(2^n). Each call spawns two more. With memoization: O(n). This is the classic 'why you need DP' example.

10. Binary search tree (balanced) insert / search / delete? Intermediate

O(log n) all three. Unbalanced BST degrades to O(n) — an adversarial input turns it into a linked list. Use AVL or red-black in production.

11. Heap (binary) — push, pop, peek? Intermediate

push: O(log n). pop (extract-min/max): O(log n). peek (top element): O(1). Building a heap from n items: O(n) using heapify, NOT O(n log n).

12. Graph BFS / DFS — time complexity? Intermediate

O(V + E) — visit every vertex once, walk every edge once. Space O(V) for the visited set + queue/stack.

13. Quicksort — best / average / worst? Intermediate

Best/average: O(n log n). Worst: O(n^2) on already-sorted input with bad pivot choice. Randomized pivot or median-of-three makes worst case unlikely.

14. Merge sort — time and space? Intermediate

O(n log n) time, guaranteed (no worst-case degradation). O(n) extra space for the merge buffer. Stable sort.

15. Heap sort — time and space? Intermediate

O(n log n) time worst case. O(1) extra space (sorts in place). Not stable.

16. Trie insert / search — time complexity? Intermediate

O(L) where L is the length of the key, NOT the number of keys stored. Space: O(N * L) worst case where N is number of keys.

17. What's the space complexity of DFS on a graph? Intermediate

O(V) for the visited set + O(h) for the recursion stack where h is the longest path. Iterative DFS with explicit stack: same O(V) worst case.

18. Dijkstra's shortest path — time complexity? Advanced

O((V + E) log V) with a binary-heap priority queue. O(V^2) with a plain array (better for dense graphs).

19. Counting sort — when does it beat O(n log n)? Advanced

O(n + k) where k is the range of input values. Beats comparison sorts when k = O(n) — e.g., sorting integers in [0, n]. Useless when k >> n.

20. Union-Find (with path compression + union by rank)? Advanced

O(α(n)) per operation — nearly constant, where α is the inverse Ackermann function. Practically O(1) for any n you'll ever see.