Computer Science and Engineering › Time Complexity › Question #15268
Single Choice Easy

QWhat is the time complexity of a breadth-first search (BFS) algorithm on a directed acyclic graph (DAG) with V vertices and E edges?

ID: #15268 Time Complexity 169 views
Question Info
#15268Q ID
EasyDifficulty
Time ComplexityTopic
Start Quiz on This Topic
 Your Answer

Choose the Best Option

Click any option to instantly check if you're correct.

  • A O(1) ✔ ✖
  • B O(log V) ✔ ✖
  • C O(V) ✔ ✖
  • D O(V + E) ✔ ✖
Correct Answer

Explanation

In a breadth-first search (BFS) algorithm on a directed acyclic graph (DAG), each vertex is visited once, and each edge is traversed once. The time complexity of BFS 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).

Today: 0 answered · 0 correct
Save progress
Free account

Want to remember what you got wrong?

Create a free account in seconds to track your score, revisit mistakes and continue Computer Science and Engineering where you left off.

  • Save your progress & streak
  • Topic-wise quizzes & scores
  • Bookmark tricky questions
  • Printable MCQ sets
Sign up free I have an account Next question
Practice smarterFree account · save progress
Sign up free
 Continue Practice
Previous Question Next Question
 Share

Share This Question

Challenge a friend or share with your study group.

 More from This Topic

Related MCQ Questions

What is the time complexity of a depth-first search (DFS) algorithm on a directed acyclic graph (DAG) with V vertices and E edges?... What is the time complexity of a merge sort algorithm for sorting an array of n elements in the worst case?... What is the time complexity of a delete operation in a binary heap in the worst case?... What is the time complexity of a selection sort algorithm for sorting an array of n elements in the worst case?... What is the time complexity of a selection sort algorithm for sorting an array of n elements in the worst case?... What is the time complexity of a binary search algorithm for finding an element in a sorted array of n elements in the worst case?... What is the time complexity of a linear search algorithm for an unsorted array of n elements in the worst case?... What is the time complexity of a bubble sort algorithm for sorting an array of n elements in the worst case?... What is the time complexity of a topological sort algorithm on a directed acyclic graph (DAG) with V vertices and E edges?... What is the time complexity of a quicksort algorithm for sorting an array of n elements in the worst case?...