Editing A* search algorithm (section)

==== Mathematical Notation ====
The worst-case complexity of A* is often described as <math display="inline">O(b^d)</math>, where <math>b</math> is the branching factor and <math display="inline">d</math> is the depth of the shallowest goal. While this gives a rough intuition, it does not precisely capture the actual behavior of A*.

A more accurate bound considers the number of nodes with <math display="inline">f(n) \leq C^{*}</math>. If <math>\varepsilon</math> is the smallest possible difference in <math display="inline">f</math>-cost between distinct nodes, then A* may expand up to:
{{center|<math>O\left(\frac{C^{*}}{\varepsilon}\right)</math>}}

This represents both the time and space complexity in the worst case.