Let \(G\) be a graph with \(n\) vertices and \(m\) edges. What is the tightest…

GATE · 2014 · CS · Set 1 · Computer Science & IT

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 802 students.

Show answer

Correct answer: C

The worked solution is available to enrolled students.

Video solution available to enrolled students.

Explore the full course: Iocl Engineers Officers Grade A Paper 2