What would be the time complexity of the BFS traversal of a graph with n vertices and n^1.25 edges?

Category: QuestionsWhat would be the time complexity of the BFS traversal of a graph with n vertices and n^1.25 edges?
Editor">Editor Staff asked 4 weeks ago

What would be the time complexity of the BFS traversal of a  graph with n vertices and n^1.25 edges?
 
(a) O(n)
 
(b) O(n^1.25)
 
(c) O(n^2.25)
 
(d) O(n*n)
 
This question is from Adjacency List topic in portion Graph of Data Structures & Algorithms I
 
I had been asked this question in semester exam.

1 Answers
Editor">Editor Staff answered 4 weeks ago

Correct choice is (b) O(n^1.25)
 
To explain: The time complexity for BFS is O(|V| + |E|) = O(n + n^1.25) = O(n^1.25).