| Data Structure | Time Complexity | Space Complexity | |||
|---|---|---|---|---|---|
| Average | Worst | ||||
| Access | Search | Insertion | Deletion | ||
| Array | Θ(1) | Θ(n) | Θ(n) | Θ(n) | O(n) |
| Stack | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) |
| Queue | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) |
| Singly-Linked List | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) |
| Doubly-Linked List | Θ(n) | Θ(n) | Θ(1) | Θ(1) | O(n) |
| Skip List | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n log(n)) |
| Hash Table | N/A |
Θ(1) | Θ(1) | Θ(1) | O(n) |
| Binary Search Tree | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n) |
| Cartesian Tree | N/A |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n) |
| B-Tree | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n) |
| Red-Black Tree | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n) |
| AVL Tree | Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
Θ(log(n)) |
O(n) |
| Algorithm | Time Complexity | Space Complexity | ||
|---|---|---|---|---|
| Best | Average | Worst | Worst | |
| Quicksort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) |
O(log(n)) |
| Mergesort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(n) |
| Heapsort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(1) |
| Bubble Sort | Ω(n) | Θ(n^2) |
O(n^2) |
O(1) |
| Insertion Sort | Ω(n) | Θ(n^2) |
O(n^2) |
O(1) |
| Selection Sort | Ω(n^2) |
Θ(n^2) |
O(n^2) |
O(1) |
| Tree Sort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) |
O(n) |
| Shell Sort | Ω(n log(n)) | Θ(n(log(n))^2) |
O(n(log(n))^2) |
O(1) |
| Bucket Sort | Ω(n+k) | Θ(n+k) | O(n^2) |
O(n) |
| Radix Sort | Ω(nk) | Θ(nk) | O(nk) | O(n+k) |
| Counting Sort | Ω(n+k) | Θ(n+k) | O(n+k) | O(k) |
| Cubesort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) |