title: Why is the complexity of A* exponential in memory?
body: <p>Wikipedia says on A* complexity the following (<a href="http://en.wikipedia.org/wiki/A*_search_algorithm" rel="noreferrer">link here</a>):</p>
  
  <blockquote>
    <p>More problematic than its time
    complexity is A*’s memory usage. In
    the worst case, it must also remember
    an exponential number of nodes.</p>
  </blockquote>
  
  <p>I fail to see this is correct because:</p>
  
  <p>Say we explore node A, with successors B, C, and D. Then we add B, C, and D to the list of open nodes, each accompanied by a reference to A, and we move A from the open nodes to the closed nodes.</p>
  
  <p>If at some time we find another path to B (say, via Q), that is better than the path through A, then all that is needed is to change B's reference to A to point to Q and update its actual cost, g (and logically f).</p>
  
  <p>Therefore, if we store in a node its name, its referring node name, and its g, h, and f scores, then the maximum amount of nodes stored is the actual amount of nodes in the graph, isn't it? I really cannot see why at any time the algorithm would need to store an amount of nodes in memory that is exponential to the length of the optimal (shortest) path.</p>
  
  <p>Could someone please explain?</p>
  
  <hr>
  
  <p><strong>edit</strong> As I understand now reading your answers, I was reasoning from the wrong viewpoint of the problem. I took for granted a <em>given</em> graph, whereas the exponential complexity refers to a an <em>conceptual</em> graph that is defined solely by a "branching factor".</p>