GATE Overflow Test Series | Algorithms | Test 2 | Question: 10

Question

Let $G$ be a graph with $n$ vertices and $m$ edges. What is the tightest upper bound on the running time on Depth First Search of $G$? (Mark all the correct options)

• A. $\Theta(m+n)$ if $G$ is represented using adjacency matrix
• B. $\Theta(m+n)$ if $G$ is represented using adjacency list
• C. $\Theta(n^2)$ if $G$ is represented using adjacency matrix
• D. $\Theta(n^2)$ if $G$ is represented using adjacency list

Answer 1

In a graph with $n$ vertices and $m$ edges, DFS has the best case time complexity of $\Theta(m+n)$ when the graph is represented in Adjacency List format. With Adjacency Matrix, the time complexity will become $\Theta(n^2).$ So, options B and C are correct.