Artificial Intelligence MCQ
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(d2) and O(d2)
B)
O(b2) and O(d2)
C)
O(d2) and O(b2)
D)
O(bd+1) and O(bd+1)

Correct Answer : Option (D) :   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.