Consider the following terminology and match List I with List II and choose…
2018
Consider the following terminology and match List I with List II and choose the correct answer from the code given below.
b= branching factor
d = depth of the shallowest solution
m= maximum depth of the search tree
l=depth limit
Table (List I – Algorithms, List II – Space Complexity)
Code:
- A.
(a) – (i), (b)-(ii), (c)-(iv), (d)-(iii)
- B.
(a) – (ii), (b)-(iii), (c)-(iv), (d)-(i)
- C.
(a) – (iii), (b)-(ii), (c)-(iv), (d)-(i)
- D.
(a) – (i), (b)-(iii), (c)-(iv), (d)-(ii)
Attempted by 108 students.
Show answer & explanation
Correct answer: B
Answer: Breadth-first search → O(b^d); Depth-first search → O(bm); Depth-limited search → O(bl); Iterative deepening search → O(bd).
Breadth-first search: uses O(b^d) space
Depth-first search: uses O(bm) space
Depth-limited search: uses O(bl) space (DFS limited to depth l)
Iterative deepening search: uses O(bd) space (each depth-first iteration to depth d uses O(bd) memory)
Why these matchings hold: Breadth-first search keeps all nodes in the frontier up to the shallowest solution level, so the number of stored nodes grows like b^d. Depth-first search stores only a single path from the root to a leaf and the unexplored siblings along that path, which scales as O(bm) where m is the maximum depth. Depth-limited search is the same as DFS but capped at depth l, giving O(bl). Iterative deepening repeatedly runs DFS to increasing depths, but each run uses DFS memory proportional to the current depth, so overall space is O(bd).
A video solution is available for this question — log in and enroll to watch it.