DSA — Complexity Analysis
Big-O Notation
How runtime and memory scale as input size n grows toward infinity. The universal language every engineer needs to speak fluently.
O(1)Constant
O(n)Linear
O(log n)Logarithmic
O(n²)Quadratic
6Classes
Complexities
Rules
Cheat Sheet
Quiz
O(1)
Constant
Array index, hash lookup, arithmetic. Same speed regardless of input size.
IDEAL
O(log n)
Logarithmic
Binary search, balanced BST ops. Double n = only +1 step.
EXCELLENT
O(n)
Linear
Single loop, array scan. One operation per element.
GOOD
O(n log n)
Linearithmic
Merge, Heap, Quick sort. Split-and-merge strategies.
FAIR
O(n²)
Quadratic
Nested loops. Bubble, Selection sort. Hurts beyond ~10k.
SLOW
O(2ⁿ)
Exponential
Brute force subset generation. Avoid entirely for n > 30.
AVOID
01
Drop Constants
Constants don't matter at extreme scale. Two passes through n is still linear growth — the 2× factor becomes noise.
O(2n) → O(n) | O(100n) → O(n)
02
Drop Non-Dominant Terms
When n is huge, n² dwarfs n. Keep only the term that grows the fastest.
O(n² + n) → O(n²) | O(n³ + n²) → O(n³)
03
Different Inputs = Different Variables
If a function takes two arrays of size a and b, don't blindly write O(n²). The loops aren't nested over the same array.
for a: for b: → O(a·b), not O(n²)
04
Sequential vs Nested: Add vs Multiply
Two sequential loops add their complexities. Two nested loops multiply them.
Sequential → O(a + b) Nested → O(a × b)
Interview tip: Always state both time AND space complexity. Mention best / worst / average when they diverge — e.g. QuickSort averages O(n log n) but degrades to O(n²) with bad pivots.
| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) |
| Hash Table | O(1) | O(1) | O(n) | O(n) |
| BST Search | O(log n) | O(log n) | O(n) | O(1) |
| BFS / DFS | O(V+E) | O(V+E) | O(V+E) | O(V) |