running times Flashcards
1
Q
Prim’s running time (naive)
A
O(mn)
2
Q
Prim’s running time (heaps)
A
O(mlogn)
3
Q
Prim’s running time (fibonacci heaps)
A
O(m + nlogn)
4
Q
Kruskal’s running time (naive)
A
O(m^2 + mn)
5
Q
Kruskal’s running time (union-find)
A
O(mlogn)
6
Q
Dijkstra’s running time (lists)
A
O(n^2)
7
Q
Dijkstra’s running time (binary heap)
A
O((m + n) logn)
8
Q
Bellman-Ford (naive)
A
O(n^3)
9
Q
Bellman-Ford (relaxations)
A
O(mn)
10
Q
Floyd-Warshall
A
O(n^3)
11
Q
Ford-Fulkerson
A
O(Fm), F - max flow
12
Q
EK #1
A
O(m^2 log n log F ) - strong polynomial
13
Q
EK #2
A
O(m^2n)
14
Q
Bipartite matching running time (FF based)
A
O(mn)
