Algorithm Complexities
Sorting Algorithms
| Algorithm | Time Complexity (Best) | Time Complexity (Average) | Time Complexity (Worst) | Space Complexity |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n2) | O(n2) | O(1) |
| Insertion Sort | O(n) | O(n2) | O(n2) | O(1) |
| Selection Sort | O(n2) | O(n2) | O(n2) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(n log n) | O(n2) | O(log n)* |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Radix Sort | O(nk)** | O(nk) | O(nk) | O(n + k) |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) |
| Bucket Sort | O(n + k) | O(n + k) | O(n2) | O(n) |
Searching Algorithms
| Algorithm | Time Complexity (Best) | Time Complexity (Average) | Time Complexity (Worst) | Space Complexity |
|---|---|---|---|---|
| Linear Search | O(1) | O(n) | O(n) | O(1) |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) |
| Jump Search | O(1) | O(√n) | O(√n) | O(1) |
| Interpolation Search | O(1) | O(log log n) | O(n) | O(1) |
| Exponential Search | O(1) | O(log n) | O(log n) | O(log n) |
Tree Traversals
| Traversal Type | Time Complexity | Space Complexity |
|---|---|---|
| Inorder | O(n) | O(h)* |
| Preorder | O(n) | O(h) |
| Postorder | O(n) | O(h) |
| Level Order | O(n) | O(w)** |
Data Structures Operations
| Data Structure | Search (Avg/Worst) | Insert (Avg/Worst) | Delete (Avg/Worst) | Space Complexity |
|---|---|---|---|---|
| Array | O(1)/O(n) | O(n)/O(n) | O(n)/O(n) | O(n) |
| Stack (Array-based) | O(n)/O(n) | O(1)/O(1) | O(1)/O(1) | O(n) |
| Queue (Array-based) | O(n)/O(n) | O(1)/O(1) | O(1)/O(1) | O(n) |
| Singly Linked List | O(n)/O(n) | O(1)/O(1) | O(1)/O(1) | O(n) |
| Doubly Linked List | O(n)/O(n) | O(1)/O(1) | O(1)/O(1) | O(n) |
| Binary Search Tree | O(log n)/O(n) | O(log n)/O(n) | O(log n)/O(n) | O(n) |
| AVL Tree | O(log n)/O(log n) | O(log n)/O(log n) | O(log n)/O(log n) | O(n) |
| Hash Table | O(1)/O(n) | O(1)/O(n) | O(1)/O(n) | O(n) |
* \(h\) is the height of the tree.
** \(w\) is the maximum width of the tree.
** \(k\) is the number of digits in the input (for Radix Sort).
No comments:
Post a Comment