UGC NET CSE | November 2017 | Part 3 | Question: 56

Question

If $b$ is the branching factor and $m$ is the maximum depth of the search tree, what is the space complexity of greedy search?

• A. $O (b+m)$
• B. $O(bm)$
• C. $O(b^m)$
• D. $O(m^b)$

Answer 1

In greedy search, we expand the node that is estimated to be closest to goal.

Here, we see that at each level, we have b nodes to choose from (since branching factor is b) and there are m such levels at max.

∴∴ The total no. of nodes to choose from = b×b×b×…m times=b^m

∴∴ Space complexity = O(b^m)

Hence option A is correct.