In the algorithm outlined in the article linked, what is the time complexity for a Breadth...
Palo Alto Networks technical mcq question, verified with a worked answer. Free to practise - no sign-up.
In the algorithm outlined in the article linked, what is the time complexity for a Breadth First Traversal of a graph?
Select any one of the following options
Show answer & explanation
Answer: A. A) O(V+E)
Breadth-first search traverses each vertex once and inspects each edge incident to it once (in directed) or twice (in undirected), resulting in O(V + E) time.
Step-by-step Derivation:
Step 1: In BFS with adjacency list representation, each vertex is enqueued and dequeued exactly once, contributing O(V).
Step 2: When dequeuing vertex u, all adjacent edges (u, v) are scanned once, summing over all vertices to O(E).
Step 3: Total time complexity = O(V + E).