If b is the branching factor and m is the maximum depth of the search tree,…
2017
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 (b.m)
- C.
O(b^m)
- D.
O(m.b)
Attempted by 112 students.
Show answer & explanation
Correct answer: C
Answer: The space complexity is O(b^m), exponential in the maximum depth m.
Explanation:
Greedy best-first search maintains a frontier (a priority queue) of all generated but not yet expanded nodes.
In the worst case the algorithm may generate all nodes up to depth m. The number of nodes at depth d grows roughly as b^d, so the frontier can grow on the order of b^m.
Because the frontier (memory) can contain that many nodes, the space complexity is O(b^m).
Note: Depth-first search uses O(b.m) space, while breadth-first and best-first (including greedy best-first in the worst case) use exponential space O(b^m).