Match List - I with List - II : Choose the correct answer from the options…

Correct matching:

• Hill climbing → O(1) — Hill climbing is a local search that keeps only the current state (and possibly a small neighborhood), so its additional space requirement is constant.

• Best-first search → O(b^d) — In the worst case best-first search can expand an exponential number of nodes similar to breadth-first search, on the order of b^d where d is solution depth.

• A* → O(b^m) — A* can, in the worst case, explore nodes up to the maximum depth m of the search tree, leading to exponential growth in time with respect to m.

• Depth-first search → O(bd) — Depth-first search stores a single path from the root to a leaf plus unexplored siblings, so its space is proportional to branching factor times depth (commonly written O(bd) or O(bm) depending on symbols used).

Summary: Hill climbing is constant-space (O(1)); best-first and A* can require exponential time in depth (O(b^d) or O(b^m) in worst cases); depth-first search has linear-in-depth space O(bd).