Let \(G\) be a graph with \(n\) vertices and \(m\) edges. What is the tightest…
2014
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?
- A.
\(\theta (n)\) - B.
\(\theta (n + m)\) - C.
\(\theta (n^2)\) - D.
\(\theta (m^2)\)
Attempted by 343 students.
Show answer & explanation
Correct answer: C
Key insight: when the graph is stored as an adjacency matrix, finding the neighbors of a vertex requires scanning its entire matrix row.
Step 1: Scanning one vertex's row takes Θ(n) time to check all possible adjacency entries.
Step 2: There are n vertices, so total time is Θ(n) × n = Θ(n^2).
Note: While Θ(n + m) is the bound for adjacency lists, it does not apply here because the matrix representation forces scanning of n entries per vertex even if m is small. Also m can be Θ(n^2), so Θ(n^2) is a tight worst-case bound.
A video solution is available for this question — log in and enroll to watch it.