Question

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.

Answer 1

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