is the ans b???

Awesome q2a theme

0 votes

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)

- O(V^3)
- O(V^2)
- O(V^2 . E)
- O(V + E)

Anyone please clarify.

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).

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)$.

8,437 questions

2,714 answers

13,238 comments

95,460 users