W związku z tym można stwierdzić, że A* bierze pod uwagę najmniejszą liczbę węzłów ze wszystkich dopuszczalnych algorytmów przeszukiwań, oczywiście pod warunkiem, że algorytmy te nie używają heurystyk dających bardziej dokładne oszacowania.
Złożoność czasowa Obliczeniowa złożoność czasowa algorytmu A* zależy od zastosowanej heurystyki. W najgorszym przypadku liczba przeszukanych węzłów rośnie wykładniczo w stosunku do długości rozwiązania (najkrótszej ścieżki), natomiast rośnie już tylko wielomianowo, jeśli funkcja heurystyki spełnia następujący warunek:
gdzie jest optymalną heurystyką, czyli zawsze podaje dokładny, rzeczywisty koszt ścieżki z do węzła końcowego. Innymi słowy, błąd funkcji nie powinien rosnąć szybciej niż logarytm „dokładnej heurystyki”
Bardziej problematyczne niż koszt czasowy jest zużycie pamięci przez A*. W najgorszym przypadku algorytm musi zapamiętać liczbę węzłów, która rośnie wykładniczo w stosunku do długości rozwiązania. Kilka wariantów algorytmu A* zostało stworzonych, by rozwiązać ten problem. Niektóre z nich to: IDA* (ang. iterative deepening A*), MA* (ang. memory-bounded A*), SMA* (ang. simplified memory-bounded A*) oraz RBFS (ang.