🎓 Computer Science • Algorithms
100% Client-Side Privacy
Algorithm & Data Structure Complexity Reference
Comprehensive cheat-sheet matrix of Best, Average, and Worst case Time and Space complexities for sorting and data structures.
Standard Sorting Algorithms Time, Space & Stability Master Reference
| Algorithm | Best Case | Average Case | Worst Case | Space | Stable | Paradigm |
|---|---|---|---|---|---|---|
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Divide & Conquer |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Divide & Conquer |
| Timsort (Python/Java/V8) | O(n) | O(n log n) | O(n log n) | O(n) | Yes | Hybrid Merge/Insertion |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Selection / Heap |
| Radix Sort (Integer keys) | O(nk) | O(nk) | O(nk) | O(n + k) | Yes | Non-Comparison Distribution |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Incremental Insertion |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Exchange |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Selection |
Algorithm Complexity Matrix
Understanding best, average, and worst-case performance trade-offs is essential for selecting the right algorithms in software engineering.
Formula & Step-by-Step Calculation
Quicksort: Avg O(n log n), Worst O(n²); Mergesort: Guaranteed O(n log n)
Comparison of divide-and-conquer sorting algorithms.
Worked Step-by-Step Examples
Example 1
What is the average time complexity to search a Hash Table vs Binary Search Tree?
Solution: Hash Table = O(1); BST = O(log n)
• Hash tables provide constant-time key hashing
Common Real-World & Academic Use Cases
- ✓ Technical coding interview preparation
- ✓ Architecture decisions for high-throughput databases
- ✓ Memory footprint optimization in embedded systems
How to Use the Algorithm & Data Structure Complexity Reference
1
Select Algorithm Category
Switch between Sorting and Data Structures tabs.
2
Inspect Performance
Review time and space guarantees.
Frequently Asked Questions
Q: Why is Mergesort preferred for linked lists?
Because Mergesort requires no random access and merges elements sequentially without extra array allocation.