1
$\begingroup$

When using the breadth-first search algorithm, is the space complexity $O(b^d)$, where $b$ is the branching factor and $d$ the length of the optimal path (assuming that there is indeed one)?

$\endgroup$
0
0
$\begingroup$

The space complexity of the breadth-first search algorithm is $O(b^d$) in the worst case, and it corresponds to the largest possible number of nodes that may be stored in the frontier at once, where the frontier is the set of nodes (or states) that you are currently considering for expansion.

You can take a look at section 3.5 (page 74) of the book Artificial Intelligence: A Modern Approach (3rd edition, by Norvig and Russell) for more info about the time and space complexity of BFS.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy