A* time complexity

Question

Wikipedia says the following on A*'s complexity:

The time complexity of A* depends on the heuristic. In the worst case, the number of nodes expanded is exponential in the length of the solution (the shortest path), but it is polynomial when the search space is a tree...

And my question is: "Is A*'s time complexity exponential? Or is it not a time complexity, but memory complexity?" If it is memory complexity, which time complexity does A* have?

Answer 1

In the worst case A* time complexity is exponential.

But, consider h(n) the estimated distance and h*(n) the exact distance remaining. If the condition | h(n) - h*(n) | < O(log *h(n) ) holds, that is, if the error of our estimate functions grows subexponential, then A* time complexity will be polynomial.

Sadly, most of the time the estimate error grows linear, so, in practice, faster alternatives are preferred, the price paid being the fact that optimality is not achieved anymore.

Answer 2

Since each expanded node is stored to avoid visiting the same node multiple times, the exponential growth of the number of expanded nodes implies exponential time and space complexity.

Please note that exponential space complexity necessary implies exponential time complexity. The inverse is not true.