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) |