Question

The time and space complexity of BFS is (For time and space complexity problems consider b as branching factor and d as depth of the search tree.)

(a) O(bd+1) and O(bd+1)

(b) O(b2) and O(d2)

(c) O(d2) and O(b2)

(d) O(d2) and O(d2)

The question was posed to me in homework.

My query is from Uninformed Search and Exploration in chapter Problem Solving of Artificial Intelligence

Answer 1

The correct answer is (a) O(bd+1) and O(bd+1)

Explanation: We consider a hypothetical state space where every state has b successors. The root of the search tree generates b nodes at the first level, each of which generates b more nodes, for a total of b2 at the second level. Each of these generates b more nodes, yielding b3 nodes at the third level, and so on. Now suppose that the solution is at depth d. In the worst case, we would expand all but the last node at level d (since the goal itself is not expanded), generating bd+1- b nodes at level d+1.