7

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?

Edward
  • 5,942
  • 4
  • 38
  • 55
Szkandy
  • 73
  • 1
  • 1
  • 5

3 Answers3

5

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.

coredump
  • 3,017
  • 6
  • 35
  • 53
3

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.

Dima Chubarov
  • 16,199
  • 6
  • 40
  • 76
  • 4
    @user1403414 I am afraid this is not quite a complete answer, since the wikipedia article says that A* is exponential in the length of the solution. This is different from the standard setting of complexity theory where the complexity is measured against the length of the input. – Dima Chubarov Jun 17 '12 at 09:50
  • 2
    It's `O((|V| + |E|) log |V|)`. It makes the most sense to describe A* complexity in terms of graph size. This answer is surprisingly poor (Wikipedia-driven perhaps? Not Cormen for sure...) – PawelP Oct 19 '14 at 18:42
0

Is A* time complexity exponential or it's memory complexity?

That extract from Wikipedia suggests that that it's referring to time complexity

James Webster
  • 31,873
  • 11
  • 70
  • 114