Explain the space complexity of interative deepening a*?
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)?
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*).