The GATE Grind

GATE 2014 CS (CS1) – Question 21

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 1 mark · Multiple choice

G has n vertices and m edges and is represented by an adjacency matrix. Find the tightest upper bound on Depth First Search running time.

  1. $\Theta(n)$
  2. $\Theta(n+m)$
  3. $\Theta(n^2)$
  4. $\Theta(m^2)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $\Theta(n^2)$

Explanation

Discovering a vertex requires scanning its n-entry matrix row to find neighbours. Across n vertices, the full traversal can inspect n²entries, regardless of how few edges exist. Therefore the tight worst-case bound is **Θ(n²), C**. The Θ(n+m) bound applies to adjacency lists.