Временная сложность A*

Википедия говорит о сложности A* следующее:

Временная сложность A* зависит от эвристики. В худшем случае количество расширенных узлов экспоненциально зависит от длины решение (кратчайший путь), но полиномиальное при поиске пространство - это дерево...

И мой вопрос: "Является ли временная сложность A* экспоненциальной? Или это не временная сложность, а сложность памяти?" Если это сложность памяти, то какую временную сложность имеет A*?