Runtime Flashcards
1
Q
What is the runtime of:DFS Runtime
A
O(n+m)
2
Q
What is the runtime of:Explore Runtime
A
O(n+m)
3
Q
What is the runtime of:BFS Runtime
A
O(n + m)
4
Q
What is the runtime of:SCC Runtime
A
O(m+n)
5
Q
What is the runtime of:Bellman Ford
A
O(nm)
6
Q
What is the runtime of:Floyd Warshall
A
O(n^3)
7
Q
What is the runtime of:Kruskal’s
A
(m log n)
8
Q
What is the runtime of:Prims
A
O(m log n)
9
Q
What is the runtime of:2-SAT
A
O(n+m)
10
Q
What is the runtime of:Ford Fulkerson
A
O(C m)
11
Q
What is the runtime of:Edmonds-Karp
A
O(nm^2)
12
Q
What is the runtime of:Explore on an undirected graph
A
O(m+n) simplifies to O(m)
13
Q
What is the runtime of:DFS on a connected graph
A
O(m+n) simplifies to O(m)
14
Q
What is the runtime of:Explore on connected MST
A
O(m+n)
15
Q
What is the runtime of:DFS on unconnected MST
A
O(m+n)
