Sorting Algorithms and Data Structures Complexity Table
Classified in Design and Engineering
Written on in 
English with a size of 3.04 KB
Sorting Algorithms Performance
| Algorithm | Best Case | Average Case | Worst Case | Space Complexity | Stable | In-place | Speed |
|---|---|---|---|---|---|---|---|
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes | Slow |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No | Yes | Slow |
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes | Slow |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes | Fast |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No | Fast |
| Quick | O(n log n) | O(n log n) | O(n²) | O(n) | No | Yes | Fast |
| Bucket | O(n+k) | O(n+k) | O(n²) | O(n+k) | Yes | No | Fast |
| Radix | O(nk) | O(nk) | O(nk) | O(n+k) | Yes | No | Fast |
Data Structure Complexity
| Data Structure | Insert() | Remove | Search() | RemoveMin() | Access | Space | Size |
|---|---|---|---|---|---|---|---|
| Dynamic Array | O(1) / O(n) | O(n) | O(n) | O(n) | O(1) | O(n) | Small |
| ArrayList | O(1) / O(n) | O(n) | O(n) | O(n) | O(n) | O(n) | Small |
| Singly Linked List | O(1) / O(n) | O(n) | O(n) | O(1) / O(n) | O(n) | O(n) | Small |
| Doubly Linked List | O(1) | O(n) | O(n) | O(n) | O(n) | O(n) | Small, Large |
| Stack (Array) | O(1) | O(n) | O(n) | N/A | O(n) | O(n) | Small, Large |
| Stack (List) | O(1) | O(n) | O(n) | N/A | O(n) | O(n) | Small, Large |
| Queue (Array) | O(1) | O(n) | O(n) | N/A | O(1) | O(n) | Small, Large |
| Queue (List) | O(1) | O(n) | O(n) | N/A | O(n) | O(n) | Small, Large |
| BST | O(log n) / O(n) | O(log n) / O(n) | O(log n) / O(n) | O(log n) | O(log n) / O(n) | O(n) | Small, Large |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | Small, Large |
| Hash Tables | O(1) / O(n) | O(1) / O(n) | O(1) / O(n) | O(n) | O(1) / O(n) | O(n) / O(n²) | Small, Large, Huge |
| Heaps | O(1) | O(1) | O(1) | N/A | O(1) | O(n) | Small, Large |