Q: What is the time complexity of a depth-first search (DFS) algorithm on a directed acyclic graph (DAG) with V vertices and E edges?

A O(1)
B O(log V)
C O(V)
D O(V + E)

Share this MCQ

Answer: D

Explanation:

In a depth-first search (DFS) algorithm on a directed acyclic graph (DAG), each vertex is visited once, and each edge is traversed once. The time complexity of DFS on a DAG is proportional to the sum of the number of vertices (V) and the number of edges (E), denoted as O(V + E).

Time Complexity

Share Above MCQ

‹ Previous Next ›

Write your comment

Learn More MCQ Questions from Data Structure Time Complexity

Q: What is the time complexity of a depth-first search (DFS) algorithm on a directed acyclic graph (DAG) with V vertices and E edges?

Report Question