38 views

Assume that the enqueuing and dequeuing of elements in BFS takes O(V) time. then what will be the time complexity of the BFS algorithm? (Assume adjacency list representation)

1. O(V^3)
2. O(V^2)
3. O(V^2 . E)
4. O(V + E)

| 38 views
0
is the ans b???
0
No, they gave the answer as a.
0
since it is adjacency list then there can be at max 2E visits at max and for each visit generally we do constant amount of work(as enqueue/dequeue take constant time) but here it takes O(V)

so time complexity should be O(2EV+V) i.e O(EV+V)

if enqueue/dequeue take constant time then time complexity is well known as O(E+V).
0
Maybe, they have considered $E=\ ^VC_2 = \frac{V*(V-1)}{2}=O(V^2)$, and after this consideration $O(EV+V)=O(V^2*V+V)=O(V^3)$.
0
But they gave Adjacency list representation so we should not consider E=O(V^2) right?
0
yah more accurate would be O(EV+V) in case of adjacency list
0
But any how we consider E=O(V) [ since it is an adjacency list ]. So it becomes O(EV + V) = O(V*V + V) = O(V^2 + V) = O(V^2), isn’t it?
0
see they should mention weather its a sparse or dense graph
0
Yes, we can consider $E=O(V^2)$ if the graph is dense.
0
yes:)