Runtime 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
(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: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)
