Database-Management-System
December 3, 2023Question 1187 – Nielit Scientist-B CS 22-07-2017
December 3, 2023Question 1193 – Nielit Scientist-B CS 22-07-2017
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on DFS of G? Assume that the graph is represented using adjacency matrix
Correct Answer: C
Question 41 Explanation:
DFS visits each vertex once and as it visits each vertex, we need to find all of its neighbours to figure out where to search next. Finding all its neighbours in an adjacency matrix requires O(V) time, so overall the running time will be O(V2).
O(n)
O(m+n)
O(n^2)
O(mn)
Subscribe
Login
0 Comments