Awesome q2a theme
0 votes
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)

Anyone please clarify.

in Algorithms by (39 points) | 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:)

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
8,437 questions
2,714 answers
13,238 comments
95,460 users