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
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.