I am studying informed search algorithms, and for Iterative Deepening A* Search, I know that the space complexity is O(d), where d is the depth of the shallowest goal node. I have tried to find out what its time complexity is, but I haven’t been able to find any exact information about it on online resources. Is the exact time complexity of IDA* Search unknown? Any insights are appreciated.
Question posted in Artificial Intelligence
ChatGBT is becoming a world-wide phenomena, try it out here.
3
Answers
Space complexity: O(d)
b: branching factor
You can find a proof and an example for the time complexity here.
Time complexity of IDA*: At IDA* you cannot speak in generality that it is O(b^d) time and thats it. Time complexity differs from searching in a binary tree or in an unbalanced tree or in a graph that has circles or infinite graphs etc.
So it depends first on the search enviroment. Now time will also depend on how many nodes have to be expanded, this depends on how many iterations you will have, which depends on what heuristic you use and how many different values the heuristic function will give. The more different values the heuristic gives the more iterations IDA* will do. Check the pseudo code for that to see, every time the f(n) value is greater than the actual threshold in an iteration it restarts iterating.
In a worst case you have to do all the possible expansions and all the iterations to the deepest point of the tree. This could happen in different ways in a binary tree or in an unbalanced tree.
Richard E. Korf, Time complexity of iterative-deepening-A∗ (2001): "The running time of IDA∗ is usually proportional to the number of nodes expanded.
This depends on the cost of an optimal solution, the number of nodes in the brute-force
search tree, and the heuristic function."
Space complexity of IDA*: O(d) space is not correct estimation not even for IDDFS. Space complexity can be estimated the same way for both, because they use depth first search that is known about that it needs much less memory than a BFS or even A* – in fact this is why IDA* was developed. The space complexity will be O(bd) for trees, because you always store only the actual path that the algorithm is exploring in an iteration, that is in the worst case could be the "deepest" point of the tree or say the bottom of the tree. Until that point you have to store all the nodes you have expanded, that is the branching factor times the "deepest level" of the tree = b*d. So it is O(bd).
Use this source to see how the creator of IDA* himself does the estimation.
Note: @David Speck’s previous answer is not even for IDA* but for the iterative deepening depth-first search (IDDFS). IDA* uses heuristic to direct the search which IDDFS does not, IDDFS is a brute-force search technique, they are not the same.
Actually, the space complexity of IDA* is not O(d). In the worst case, it will be like a simple DFS and it will have O(b*d) with:
Now in the best case, thanks to the heuristics admissibility and consistency, the space complexity will be O(b * C*/e) with
For the time complexity, it is like A* with O(b^d).