📈 Growth Rates Explained

Big O describes how an algorithm's runtime or memory usage scales as input size n grows. From fastest to slowest:

O(1)
Constant
Same time regardless of input size. Hash map lookup, array index access, push/pop on a stack.
O(log n)
Logarithmic
Halves the problem each step. Binary search, balanced BST operations, heap insert.
O(n)
Linear
Touches every element once. Linear search, single-pass array scan, BFS/DFS traversal.
O(n log n)
Linearithmic
Divide-and-conquer sorts. Merge sort, heap sort, quick sort (average), TimSort.
O(n²)
Quadratic
Nested loops over input. Bubble sort, selection sort, insertion sort (worst), brute-force pair checks.
O(2ⁿ)
Exponential
Doubles with each added element. Recursive Fibonacci (naive), subset generation, backtracking without pruning.
O(n!)
Factorial
All permutations. Travelling salesman brute force, generating all permutations of n items.

📊 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

O(1)
O(log n)
O(n)
O(n log n)
O(n²)
O(2ⁿ)

🗂️ 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
AvgWorst AvgWorst AvgWorst AvgWorst 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/AN/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/AN/A O(n)O(n) O(log n)O(log n) O(log n)O(log n) O(n)
Trie N/AN/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 n items is O(n). Nested loops multiply: two nested loops over n is 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 h is 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 str concatenation 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.
Africa & India's Best AI Academy
🤖 AI-first 🎓 Placement Assistance

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 →