Let G be a graph with n vertices and m edges. What is the tightest upper

bound on the running time of Depth First Search on G, when G is

represented as an adjacency matrix ?

- Θ(n)
- Θ(n + m)
- Θ(n2)
- Θ(m2)

Let G be a graph with n vertices and m edges. What is the tightest upper

bound on the running time of Depth First Search on G, when G is

represented as an adjacency matrix ?

- Θ(n)
- Θ(n + m)
- Θ(n2)
- Θ(m2)

Option C is correct. The tight upper bound is n2, because each vertex may be connected to every other vertex in the worst case, i.e. fully connected graph.