Graph Runtimes Flashcards
What is the runtime of:
DFS Runtime
O(n+m)
What is the runtime of:
Explore Runtime
O(n+m)
What is the runtime of:
BFS Runtime
O(n + m)
What is the runtime of:
SCC Runtime
O(m+n)
What is the runtime of:
Bellman Ford
O(nm)
What is the runtime of:
Floyd Warshall
O(n^3)
What is the runtime of:
Kruskal’s
O(m log n)
What is the runtime of:
Prims
O(m log n)
What is the runtime of:
2-SAT
O(n+m)
What is the runtime of:
Ford Fulkerson
O(C m)
What is the runtime of:
Edmonds-Karp
O(nm^2)
What is the runtime of:
Explore on an undirected graph
O(m+n) simplifies to O(m)
What is the runtime of:
DFS on a connected graph
O(m+n) simplifies to O(m)
What is the runtime of:
Explore on connected MST
O(m+n)
What is the runtime of:
DFS on unconnected MST
O(m+n)
What is the runtime of:
traversing a full graph
O(m+n)
Reference: https://edstem.org/us/courses/50892/discussion/4320477
What is the runtime of:
reversing a full graph
O(m+n)
Reference: https://edstem.org/us/courses/50892/discussion/4320477
What is the runtime of:
Accessing a Set?
O(n)
What is the runtime of:
copying a full graph
O(m+n)
Reference: https://edstem.org/us/courses/50892/discussion/4320477
What is the runtime of:
iterating, checking, reading, removing, working on all vertices (or subset)
O(n)
Reference: https://edstem.org/us/courses/50892/discussion/4320477
What is the runtime of:
checking, reading, or removing one edge
O(n) or O(m)
Reference: https://edstem.org/us/courses/50892/discussion/4320477
What is the runtime of:
iterating, checking, reading, removing, working on all edges
O(n+m)
What is the runtime of:
Running an O(m+n) black-box algorithm on a MST which is connected
O(m)
What is the runtime of:
Running an O(m+n) black-box algorithm on a Max Flow which is connected
O(m)
What is the runtime of:
Accessing an edge property such as a weight
O(1)
What is the runtime of:
Running DFS on a disconnected graph?
O(m+n)
