| Problem |
Description |
O(n) |
Ω(n) |
Θ(n) |
| Average |
Worst |
| Matrix |
| General Matrix Multiplication |
|
O(n3) |
O(n3) |
|
|
| Strassen's Matrix Multiplication |
|
O(nlog27) = O(n2.81) |
|
|
|
| Best Matrix Multiplication |
|
O(n2.376) |
O(n2.376) |
|
|
| |
| Sorting |
| Selection Sort |
|
O(n2) |
O(n2) |
|
|
| Bubble Sort |
|
O(n2) |
O(n2) |
|
|
| Insertion Sort |
|
O(n2) |
O(n2) |
|
|
| Shell Sort |
|
O(n3/2) |
O(n3/2) |
|
|
| Quick Sort |
|
O(nlog(n)) |
O(n2) |
|
|
| Merge Sort |
|
O(nlog(n)) |
O(nlog(n)) |
|
|
| Heap Sort |
|
O(nlog(n)) |
O(nlog(n)) |
|
|
| Graph Theory |
| Shortest Path |
Single-Sourse
(unweighted graph) |
|
O(n+m) using BFS |
|
|
|
Single-Sourse
(Dijstra's algorithm)
(simple undirected weighted)
(non-negative weight edge) |
find the length of the shortest path between two vertices in a connected simple undirected weighted graph |
O(mlog(n))similar to Prim's MST |
|
|
|
| Bellem-Ford (negative weighted edge OK, but no negative
weighted cycle) |
Single source shortest path in both directed and undirected graph, n vertices, m edges |
O(mn) |
|
|
|
| Single pair shortest path |
|
O(n) |
|
|
|
| All-Pairs Shortest paths (Floyd-Warshall) use dynamic
programming |
|
O(n3), O(n2) space |
|
|
|
| Minimum Spanning Tree |
| Kruskal |
Find the minimum spanning tree (use heap) |
O(mlog(n)) use binary heap
O(m+nlog(n)) use Fibonacci heap |
|
|
|
| Prim |
Find the minimum spanning tree |
O(mlog(n)) use binary head
O(m+nlog(n)) use Fibonacci heap |
|
|
|
| Others |
| Topological Sort |
|
O(m+n) |
|
|
|
| Breadth First Search |
|
O(m+n) |
|
|
|
| Depth First Search |
|
O(m+n) |
|
|
|