Graph Runtimes

Question 1

What is the runtime of:
DFS Runtime

Answer 1

O(n+m)

Question 2

What is the runtime of:
Explore Runtime

Answer 2

O(n+m)

Question 3

What is the runtime of:
BFS Runtime

Answer 3

O(n + m)

Question 4

What is the runtime of:
SCC Runtime

Answer 4

O(m+n)

Question 5

What is the runtime of:
Bellman Ford

Answer 5

O(nm)

Question 6

What is the runtime of:
Floyd Warshall

Answer 6

O(n^3)

Question 7

What is the runtime of:
Kruskal’s

Answer 7

O(m log n)

Question 8

What is the runtime of:
Prims

Answer 8

O(m log n)

Question 9

What is the runtime of:
2-SAT

Answer 9

O(n+m)

Question 10

What is the runtime of:
Ford Fulkerson

Answer 10

O(C m)

Question 11

What is the runtime of:
Edmonds-Karp

Answer 11

O(nm^2)

Question 12

What is the runtime of:
Explore on an undirected graph

Answer 12

O(m+n) simplifies to O(m)

Question 13

What is the runtime of:
DFS on a connected graph

Answer 13

O(m+n) simplifies to O(m)

Question 14

What is the runtime of:
Explore on connected MST

Answer 14

O(m+n)

Question 15

What is the runtime of:
DFS on unconnected MST

Answer 15

O(m+n)

Question 16

What is the runtime of:
traversing a full graph

Answer 16

O(m+n)

Reference: https://edstem.org/us/courses/50892/discussion/4320477

Question 17

What is the runtime of:
reversing a full graph

Answer 17

O(m+n)

Reference: https://edstem.org/us/courses/50892/discussion/4320477

Question 18

What is the runtime of:
Accessing a Set?

Answer 18

O(n)

Question 19

What is the runtime of:
copying a full graph

Answer 19

O(m+n)

Reference: https://edstem.org/us/courses/50892/discussion/4320477

Question 20

What is the runtime of:
iterating, checking, reading, removing, working on all vertices (or subset)

Answer 20

O(n)

Reference: https://edstem.org/us/courses/50892/discussion/4320477

Question 21

What is the runtime of:
checking, reading, or removing one edge

Answer 21

O(n) or O(m)

Reference: https://edstem.org/us/courses/50892/discussion/4320477

Question 22

What is the runtime of:
iterating, checking, reading, removing, working on all edges

Answer 22

O(n+m)

Question 23

What is the runtime of:
Running an O(m+n) black-box algorithm on a MST which is connected

Answer 23

O(m)

Question 24

What is the runtime of:
Running an O(m+n) black-box algorithm on a Max Flow which is connected

Answer 24

O(m)

Question 25

What is the runtime of:
Accessing an edge property such as a weight

Answer 25

O(1)

Question 26

What is the runtime of:
Running DFS on a disconnected graph?

Answer 26

O(m+n)