title: A* time complexity
body: <p>Wikipedia says the following on A*'s complexity:</p>
  
  <blockquote>
    <p>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...</p>
  </blockquote>
  
  <p>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?</p>