0
$\begingroup$

When using iterative deepening, is the space complexity, $O(d)$, where $b$ is the branching factor and $d$ the length of the optimal path (assuming that there is indeed one)?

$\endgroup$
0
$\begingroup$

As stated in my other answers here and here, the space complexity of these search algorithms is calculated by looking at the largest possible number of nodes that you may need to save in the frontier during the search.

Iterative deepening search (IDS) is a search algorithm that iteratively uses depth-first search (DFS), which has a space complexity of $O(bm)$, where $m$ is the maximum depth, with progressively bigger depths, and it turns out that its space complexity is $O(bd)$.

(Note that there is also the informed version of IDS, which uses the informed search algorithm A*, rather than DFS, known as iterative deepening A*).

$\endgroup$

Your Answer

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