Correct : Graph Theory

The question asks for the tightest upper bound for Depth First Search (DFS) when the graph is represented using an adjacency matrix.
Analyze the Options:
A) θ(n): DFS visits all n vertices, but with an adjacency matrix, we must check all possible vertices in each row. Therefore, θ(n) is not sufficient.
B) θ(n + m): This is the typical DFS complexity when an adjacency list is used. It is not the complexity for an adjacency matrix.
C) θ(n²): In an adjacency matrix, each vertex has a row containing n entries. DFS may need to examine all n entries for each of the n vertices. Therefore, the total running time is θ(n × n) = θ(n²).
Example: If a graph has 5 vertices, the adjacency matrix has 5 × 5 = 25 entries. DFS may need to check all 25 entries to determine which vertices are connected.
D) θ(m²): The running time of DFS with an adjacency matrix depends on the number of vertices, not the square of the number of edges.
Correct Answer: C) θ(n²)