Complexity Analysis Reference
Essential reference for algorithm complexity analysis including time and space complexity, best/worst/average cases, and practical analysis techniques.
complexity-analysistime-complexityspace-complexitybig-oalgorithm-analysis
Cheat Sheet Overview
Quick reference and study metrics
20 minutes
Reading Time
8
Sections
0
Downloads
📚algorithm-analysis
Category
Enhanced SEO fields
seo_title: "Complexity Analysis Cheat Sheet: Time & Space Complexity" seo_description: "Master algorithm complexity analysis with this comprehensive reference covering Big O notation, time/space complexity, and practical analysis techniques." seo_keywords: ["complexity analysis cheat sheet", "time complexity analysis", "space complexity", "Big O notation", "algorithm performance", "complexity theory"] canonical_url: "https://clelandco.com/cheat-sheets/algorithm-analysis/complexity-analysis" cover_image: "/images/cheat-sheets/algorithm-analysis/complexity-analysis-cover.jpg" target_audience: "Computer Science Students, Software Engineers, Algorithm Analysts" content_type: "reference-guide" prerequisites: ["Basic mathematics", "Algorithm fundamentals"] sectionCount: 8 downloadCount: 0
Complexity Analysis & Big O
🎯 Complexity Hierarchy (Fast → Slow)
Common Complexity Classes
| Notation | Name | Example | n=10 | n=100 | n=1,000 | n=10,000 |
|---|---|---|---|---|---|---|
| O(1) | Constant | Hash lookup | 1 | 1 | 1 | 1 |
| O(log n) | Logarithmic | Binary search | 3 | 7 | 10 | 13 |
| O(n) | Linear | Array scan | 10 | 100 | 1K | 10K |
| O(n log n) | Linearithmic | Merge sort | 30 | 700 | 10K | 130K |
| O(n²) | Quadratic | Bubble sort | 100 | 10K | 1M | 100M |
| O(n³) | Cubic | Floyd-Warshall | 1K | 1M | 1B | 1T |
| O(2^n) | Exponential | Subset enumeration | 1K | 10³⁰ | 10³⁰⁰ | 10³⁰⁰⁰ |
| O(n!) | Factorial | Brute force TSP | 3.6M | 10¹⁵⁷ | 10²⁵⁶⁷ | 10³⁵⁶⁵⁹ |
⏱️ Practical Time Limits (1 Second Execution)
Maximum Input Size by Complexity
| Time Complexity | Max n (1 sec) | Max n (1 min) | Algorithm Examples |
|---|---|---|---|
| O(1) | ∞ | ∞ | Hash table operations, array access |
| O(log n) | ~10¹⁸ | ~10¹⁸ | Binary search, balanced BST operations |
| O(n) | ~10⁸ | ~6×10⁹ | Linear search, single loop |
| O(n log n) | ~10⁶ | ~10⁷ | Merge sort, heap sort, efficient algorithms |
| O(n²) | ~10⁴ | ~2.5×10⁵ | Bubble sort, simple DP, nested loops |
| O(n³) | ~500 | ~4×10³ | Floyd-Warshall, matrix multiplication |
| O(2ⁿ) | ~25 | ~35 | Subset enumeration, some backtracking |
| O(n!) | ~12 | ~15 | Brute force permutations, TSP |
📊 Algorithm Complexity Reference
Sorting Algorithms
| Algorithm | Best | Average | Worst | Space | Stable | In-Place |
|---|---|---|---|---|---|---|
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ | ✅ |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ | ❌ |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ | ✅ |
| 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) | ❌ | ✅ |
| Radix Sort | O(d·n) | O(d·n) | O(d·n) | O(n+k) | ✅ | ❌ |
Search Algorithms
| Algorithm | Data Structure | Time | Space | Prerequisites |
|---|---|---|---|---|
| Linear Search | Unsorted array | O(n) | O(1) | None |
| Binary Search | Sorted array | O(log n) | O(1) | Sorted data |
| Hash Table Lookup | Hash table | O(1) avg | O(n) | Good hash function |
| BST Search | Balanced BST | O(log n) | O(1) | Balanced tree |
| BFS | Graph | O(V + E) | O(V) | Graph representation |
| DFS | Graph | O(V + E) | O(V) | Graph representation |
Dynamic Programming Problems
| Problem | Time Complexity | Space Complexity | Optimization Possible |
|---|---|---|---|
| Fibonacci | O(n) | O(n) → O(1) | Rolling variables |
| LCS (2 strings) | O(nm) | O(nm) → O(min(n,m)) | Rolling array |
| Edit Distance | O(nm) | O(nm) → O(min(n,m)) | Rolling array |
| Knapsack 0-1 | O(nW) | O(nW) → O(W) | 1D array |
| Coin Change | O(nS) | O(nS) → O(S) | 1D array |
| Matrix Chain | O(n³) | O(n²) | Knuth optimization possible |
| Optimal BST | O(n³) | O(n²) | Knuth optimization possible |
Graph Algorithms
| Algorithm | Time Complexity | Space Complexity | Use Case |
|---|---|---|---|
| BFS | O(V + E) | O(V) | Unweighted shortest path |
| DFS | O(V + E) | O(V) | Graph traversal, connectivity |
| Dijkstra's | O((V + E) log V) | O(V) | Non-negative weighted shortest path |
| Bellman-Ford | O(VE) | O(V) | Negative weights, cycle detection |
| Floyd-Warshall | O(V³) | O(V²) | All pairs shortest paths |
| Kruskal's MST | O(E log E) | O(V) | Minimum spanning tree |
| Prim's MST | O((V + E) log V) | O(V) | Minimum spanning tree |
| Topological Sort | O(V + E) | O(V) | DAG ordering |
🧮 Complexity Analysis Techniques
Master Theorem for Divide & Conquer
For recurrences of the form:
| Case | Condition | Solution | Example |
|---|---|---|---|
| Case 1 | f(n) = O(n^c) where c < log_b(a) | T(n) = Θ(n^log_b(a)) | T(n) = 8T(n/2) + n² |
| Case 2 | f(n) = Θ(n^c log^k n) where c = log_b(a) | T(n) = Θ(n^c log^(k+1) n) | T(n) = 2T(n/2) + n |
| Case 3 | f(n) = Ω(n^c) where c > log_b(a) | T(n) = Θ(f(n)) | T(n) = 2T(n/2) + n² |
Common Recurrence Patterns
| Recurrence | Solution | Algorithm Example |
|---|---|---|
| T(n) = T(n-1) + O(1) | O(n) | Linear search, factorial |
| T(n) = T(n-1) + O(n) | O(n²) | Selection sort, insertion sort |
| T(n) = 2T(n/2) + O(1) | O(n) | Binary tree traversal |
| T(n) = 2T(n/2) + O(n) | O(n log n) | Merge sort, quick sort (avg) |
| T(n) = T(n/2) + O(1) | O(log n) | Binary search |
| T(n) = 2T(n-1) + O(1) | O(2^n) | Naive Fibonacci, subset enumeration |
📝 Loop Analysis Quick Rules
# Single loop over n elements
for i in range(n): # O(n)
# constant work
# Nested loops
for i in range(n): # O(n²)
for j in range(n):
# constant work
# Loop with halving
while n > 1: # O(log n)
n = n // 2
# constant work
# Loop with doubling
i = 1
while i < n: # O(log n)
i = i * 2
# constant work
# Dependent nested loops
for i in range(n): # O(n²)
for j in range(i): # Note: j depends on i
# constant work
💾 Space Complexity Analysis
Space Complexity Categories
| Space Usage | Notation | Example | Notes |
|---|---|---|---|
| Constant | O(1) | Variables, pointers | Size doesn't grow with input |
| Logarithmic | O(log n) | Recursion stack (balanced) | Recursive calls on halved input |
| Linear | O(n) | Arrays, lists | Proportional to input size |
| Quadratic | O(n²) | 2D arrays, matrices | Nested data structures |
Common Space Optimizations
# Space-optimized Fibonacci
def fibonacci_optimized(n):
if n <= 1: return n
prev, curr = 0, 1
for i in range(2, n + 1):
prev, curr = curr, prev + curr
return curr
# Space: O(1) instead of O(n)
# Space-optimized DP (rolling array)
def knapsack_optimized(weights, values, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
# Space: O(W) instead of O(nW)
🚀 Performance Tips
When to Choose Different Complexities
- O(1): Hash tables for frequent lookups
- O(log n): Binary search in sorted data
- O(n): Single pass algorithms, unavoidable for reading input
- O(n log n): Efficient sorting, divide-and-conquer
- O(n²): Small datasets, simple implementations
- O(2ⁿ): Small datasets, exhaustive search needed
- O(n!): Very small datasets, permutation problems
Red Flags in Complexity
⚠️ Avoid these patterns for large inputs:
- Nested loops without early termination
- Recursive calls without memoization
- String concatenation in loops
- Frequent array resizing
- Unnecessary sorting in inner loops