Algorithm Time Complexity Overview
K
I hate bird
Note:
The following complexities represent typical cases for commonly used algorithms and data structures.
Actual performance may vary depending on input size, data distribution, and problem constraints.
1. Sorting Algorithms
| Algorithm | Average Time Complexity | Worst Time Complexity | Space Complexity |
| Bubble Sort | O(N²) | O(N²) | O(1) |
| Selection Sort | O(N²) | O(N²) | O(1) |
| Insertion Sort | O(N²) | O(N²) | O(1) |
| Merge Sort | O(N log N) | O(N log N) | O(N) |
| Quick Sort | O(N log N) | O(N²) | O(log N) |
| Heap Sort | O(N log N) | O(N log N) | O(1) |
| Counting Sort | O(N + K) | O(N + K) | O(K) |
| Radix Sort | O(NK) | O(NK) | O(N + K) |
2. Searching Algorithms
| Algorithm | Time Complexity |
| Linear Search | O(N) |
| Binary Search | O(log N) |
| Hash Search (Map) | O(1) average / O(N) worst |
3. Data Structure Operations
Arrays / Vectors
- Access: O(1)
- Search: O(N)
- Insert/Delete (middle): O(N)
- Insert/Delete (end): O(1) amortized
Stack / Queue
- Push / Pop: O(1)
- Search: O(N)
Heap (Priority Queue)
- Insert: O(log N)
- Extract Min/Max: O(log N)
- Build Heap: O(N)
Hash Map (unordered_map)
- Insert/Search/Delete: O(1) average, O(N) worst
4. Graph Algorithms
| Algorithm | Time Complexity (V = vertices, E = edges) |
| BFS / DFS | O(V + E) |
| Dijkstra (heap) | O((V + E) log V) |
| Floyd-Warshall | O(V³) |
| Kruskal (MST) | O(E log E) |
| Prim (MST, heap) | O(E log V) |
5. Dynamic Programming
- Fibonacci (Top-down/Bottom-up): O(N)
- LCS (Longest Common Subsequence): O(N × M)
- 0/1 Knapsack: O(N × W) (N = items, W = weight capacity)
- LIS (Longest Increasing Subsequence):
- Basic DP: O(N²)
- Optimized with Binary Search: O(N log N)
6. String Algorithms
| Algorithm | Time Complexity |
| KMP Pattern Search | O(N + M) |
| Rabin-Karp | O(N + M) average / O(NM) worst |
| Z-Algorithm | O(N + M) |
| Trie Insert/Search | O(L) (L = length of string) |