📊 Big-O Complexity Cheat Sheet
Comprehensive reference for time and space complexity of common data structures and sorting algorithms. Essential for algorithm analysis, performance optimization, and technical interviews.
Data Structure Operations
Time and space complexity for common operations
| Data Structure | Access | Search | Insertion | Deletion | Space |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) |
| Queue | O(n) | O(n) | O(1) | O(1) | O(n) |
| Singly-Linked List | O(n) | O(n) | O(1) | O(1) | O(n) |
| Doubly-Linked List | O(n) | O(n) | O(1) | O(1) | O(n) |
| Skip List | O(log n) | O(log n) | O(log n) | O(log n) | O(n log n) |
| Hash Table | N/A | O(1) | O(1) | O(1) | O(n) |
| Binary Search Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Cartesian Tree | N/A | O(log n) | O(log n) | O(log n) | O(n) |
| B-Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Red-Black Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Splay Tree | N/A | O(log n) | O(log n) | O(log n) | O(n) |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| KD Tree | N/A | O(log n) | O(log n) | O(log n) | O(n) |
🎯 Algorithm Selection Guide
When to Use Each Data Structure
Arrays
Use when you need fast random access and know the size beforehand
Hash Tables
Ideal for key-value storage with O(1) average access time
Binary Search Trees
Best for maintaining sorted data with efficient search/insert/delete
Linked Lists
Use when you need frequent insertions/deletions at arbitrary positions
Sorting Algorithm Recommendations
General Purpose: Quicksort/Mergesort
Excellent average performance for most datasets
Nearly Sorted Data: Insertion Sort
O(n) performance on nearly sorted arrays
Memory Constrained: Heapsort
O(1) space complexity with guaranteed O(n log n) time
Integer Data: Radix Sort
Linear time sorting for integers within a known range
📝 Key Considerations
Performance
- • Consider both time and space complexity
- • Average case often more important than worst case
- • Cache performance matters in practice
Data Characteristics
- • Size of the dataset
- • Distribution of data
- • Frequency of operations
Requirements
- • Stability requirements for sorting
- • Memory constraints
- • Real-time vs batch processing