Sorting
| Algorithm | Time Complexity | Space Complexity | ||
|---|---|---|---|---|
| Best | Average | Worst | Worst | |
| Selection Sort | O(n2) | O(n2) | O(n2) | O(1) |
| Bubble Sort | O(n) | O(n2) | O(n2) | O(1) |
| Insertion Sort | O(n) | O(n2) | O(n2) | O(1) |
| Heap Sort | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| Quick Sort | O(n log(n)) | O(n log(n)) | O(n2) | O(n) |
| Merge Sort | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |
Common Data Structures
Best TC
| Data structure | Access | Search | Insertion | Deletion |
|---|---|---|---|---|
| Array | O(1) | O(1) | O(1) | O(1) |
| Stack | O(1) | O(1) | O(1) | O(1) |
| Queue | O(1) | O(1) | O(1) | O(1) |
| Singly Linked list | O(1) | O(1) | O(1) | O(1) |
| Doubly Linked List | O(1) | O(1) | O(1) | O(1) |
| Hash Table | O(1) | O(1) | O(1) | O(1) |
| Binary Search Tree | O(log n) | O(log n) | O(log n) | O(log n) |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) |
| B Tree | O(log n) | O(log n) | O(log n) | O(log n) |
| Red Black Tree | O(log n) | O(log n) | O(log n) | O(log n) |
Worst TC
| Data structure | Access | Search | Insertion | Deletion |
|---|---|---|---|---|
| Array | O(1) | O(N) | O(N) | O(N) |
| Stack | O(N) | O(N) | O(1) | O(1) |
| Queue | O(N) | O(N) | O(1) | O(1) |
| Singly Linked list | O(N) | O(N) | O(N) | O(N) |
| Doubly Linked List | O(N) | O(N) | O(1) | O(1) |
| Hash Table | O(N) | O(N) | O(N) | O(N) |
| Binary Search Tree | O(N) | O(N) | O(N) | O(N) |
| AVL Tree | O(log N) | O(log N) | O(log N) | O(log N) |
| Binary Tree | O(N) | O(N) | O(N) | O(N) |
| Red Black Tree | O(log N) | O(log N) | O(log N) | O(log N) |
Avg TC
| Data structure | Access | Search | Insertion | Deletion |
|---|---|---|---|---|
| Array | O(1) | O(N) | O(N) | O(N) |
| Stack | O(N) | O(N) | O(1) | O(1) |
| Queue | O(N) | O(N) | O(1) | O(1) |
| Singly Linked list | O(N) | O(N) | O(1) | O(1) |
| Doubly Linked List | O(N) | O(N) | O(1) | O(1) |
| Hash Table | O(1) | O(1) | O(1) | O(1) |
| Binary Search Tree | O(log N) | O(log N) | O(log N) | O(log N) |
| AVL Tree | O(log N) | O(log N) | O(log N) | O(log N) |
| B Tree | O(log N) | O(log N) | O(log N) | O(log N) |
| Red Black Tree | O(log N) | O(log N) | O(log N) | O(log N) |