📈 Growth Rates Explained
Big O describes how an algorithm's runtime or memory usage scales as input size n grows. From fastest to slowest:
📊 Visual Comparison
How these growth rates compare at different input sizes. The chart uses a log scale for the y-axis so all rates are visible.
Operations Count at n = 10, 100, 1000
🗂️ Data Structure Operations
Average and worst-case time complexity for common operations on the data structures covered in this track.
| Data Structure | Access | Search | Insert | Delete | Space | ||||
|---|---|---|---|---|---|---|---|---|---|
| Avg | Worst | Avg | Worst | Avg | Worst | Avg | Worst | Worst | |
| Array | O(1) | O(1) | O(n) | O(n) | O(n) | O(n) | O(n) | O(n) | O(n) |
| Linked List | O(n) | O(n) | O(n) | O(n) | O(1) | O(1) | O(1) | O(1) | O(n) |
| Hash Map | N/A | N/A | O(1) | O(n) | O(1) | O(n) | O(1) | O(n) | O(n) |
| Stack | O(n) | O(n) | O(n) | O(n) | O(1) | O(1) | O(1) | O(1) | O(n) |
| Queue | O(n) | O(n) | O(n) | O(n) | O(1) | O(1) | O(1) | O(1) | O(n) |
| BST | O(log n) | O(n) | O(log n) | O(n) | O(log n) | O(n) | O(log n) | O(n) | O(n) |
| Heap | N/A | N/A | O(n) | O(n) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Trie | N/A | N/A | O(k) | O(k) | O(k) | O(k) | O(k) | O(k) | O(n·k) |
k = length of the key/word. BST worst cases occur when the tree is completely unbalanced (essentially a linked list). Hash map worst cases occur with excessive collisions.
🔄 Sorting Algorithms
Time and space complexity of sorting algorithms covered in the track. "Stable" means equal elements keep their original relative order.
| 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 |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes |
| TimSort | O(n) | O(n log n) | O(n log n) | O(n) | Yes |
k = range of input values (for Counting Sort). TimSort is Python's built-in sort — a hybrid of merge sort and insertion sort.
🌐 Graph Algorithms
Time and space complexity for graph algorithms. V = vertices, E = edges.
| Algorithm | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| BFS | O(V + E) | O(V) | Unweighted shortest path, level-order traversal |
| DFS | O(V + E) | O(V) | Cycle detection, connected components, topological sort |
| Dijkstra | O((V + E) log V) | O(V) | Single-source shortest path, non-negative weights only |
| Bellman-Ford | O(V · E) | O(V) | Handles negative weights, detects negative cycles |
| Kahn's Topo Sort | O(V + E) | O(V) | BFS-based, DAGs only, detects cycles |
🧩 Common Interview Patterns
Typical complexity of frequently-used coding interview patterns.
| Pattern | Typical Time | Typical Space | When to Use |
|---|---|---|---|
| Two Pointers | O(n) | O(1) | Sorted arrays, pair sums, palindrome checks, partitioning |
| Sliding Window | O(n) | O(1) or O(k) | Subarray/substring problems, max sum, longest unique substring |
| Binary Search | O(log n) | O(1) | Sorted data, search space reduction, "minimum that satisfies" |
| Hash Map Lookup | O(n) | O(n) | Frequency counting, two-sum, grouping, deduplication |
| Dynamic Programming | O(n) to O(n²) | O(n) to O(n²) | Overlapping subproblems, optimal substructure (knapsack, LCS, paths) |
| Backtracking | O(2ⁿ) or O(n!) | O(n) | Permutations, combinations, constraint satisfaction (N-Queens, Sudoku) |
💡 Tips for Analyzing Complexity in Interviews
Quick Analysis Rules
- 1A single loop over
nitems is O(n). Nested loops multiply: two nested loops overnis O(n²). - 2If you halve the input each step (binary search, balanced BST), it is O(log n).
- 3Divide-and-conquer that does O(n) work per level with O(log n) levels gives O(n log n) (merge sort).
- 4Hash map lookups are O(1) amortized. Using a hash map inside a loop keeps the loop at O(n) total.
- 5Recursive calls that branch twice per level produce O(2ⁿ). Memoization can reduce this to O(n) or O(n²).
- 6Space complexity includes the call stack. Recursive DFS on a tree uses O(h) space where
his tree height. - 7Always state both time and space complexity. Interviewers expect both.
- 8Drop constants and lower-order terms:
O(2n + 100)simplifies to O(n).
Common Mistakes to Avoid
- !Saying
O(n)when you have a sort step — sorting alone is already O(n log n). - !Forgetting that
strconcatenation in a loop in Python is O(n²) total because strings are immutable. Use"".join(). - !Confusing amortized O(1) (e.g., dynamic array append) with worst-case O(1) (e.g., hash map with no collisions).
- !Ignoring the space used by the recursion call stack. A recursive DFS on a skewed tree uses O(n) space.
Know the complexities.
Now ace the interview.
Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses →