📊 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.
📚 Practice what you've learned with our Big-O Flashcards
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