Project ForgeAlgorithms
Complexity Analysis
GATE 2014
Medium
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Θ(n)
- BΘ(n+m)
- Θ(n²)
- DΘ(m²)
Explanation
With an adjacency-LIST representation, DFS is Θ(n+m) since it only ever scans a vertex's actual neighbours. But with an adjacency MATRIX, finding a vertex's neighbours means scanning its entire row of n entries, regardless of how many real edges it has — so each of the n vertices costs Θ(n) to process, giving Θ(n²) overall (independent of m).
Source: GATE CS 2014 (Session 1) (2014)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.