Question

What is the space complexity of Depth-first search?

(a) O(b)

(b) O(bl)

(c) O(m)

(d) O(bm)

The question was posed to me during a job interview.

My question is from Uninformed Search Strategy topic in chapter Problem Solving of Artificial Intelligence

Select the correct answer from above options

Interview Questions and Answers, Database Interview Questions and Answers for Freshers and Experience

Answer 1

The correct choice is (d) O(bm)

Easy explanation: O(bm) is the space complexity where b is the branching factor and m is the maximum depth of the search tree.