in Algorithms retagged by
1,458 views
0 votes
0 votes

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 of $G$, when $G$ is represented using adjacency matrix?

  1. $O(n)$
  2. $O(m+n)$
  3. $O(n^2)$
  4. $O(mn)$
in Algorithms retagged by
by
1.5k views

1 comment

0
0

2 Answers

1 vote
1 vote
Option C

Let G be a graph with n vertices and m edges. the tightest upper bound on the running time of Depth First Search of G,

when G is represented as an adjacency matrix=$O(n^{2})$

when G is represented as an adjacency list=$O(n+m)$
0 votes
0 votes
option c

adjacency matrix    O(N^2)
Answer:

Related questions