Результатом применения любого алгоритма решения задачи является либо неудачное завершение, либо получение решения. (Некоторые алгоритмы могут входить в бесконечный цикл и не возвращать никакого результата.) Мы будем оценивать производительность алгоритма с помощью четырех показателей, описанных ниже.

•    Полнота. Гарантирует ли алгоритм обнаружение решения, если оно имеется?

•    Оптимальность. Обеспечивает ли данная стратегия нахождение оптимального решения, в соответствии с определением?

•    Временная сложность. За какое время алгоритм находит решение?

•    Пространственная сложность. Какой объем памяти необходим для осуществления поиска?

Временная и пространственная сложность всегда анализируются с учетом определенного критерия измерения сложности задачи. В теоретической компьютерной науке типичным критерием является размер графа пространства состояний, поскольку этот граф рассматривается как явно заданная структура данных, которая является входной для программы поиска. (Примером этого может служить карта Румынии.) В искусственном интеллекте, где граф представлен неявно с помощью начального состояния и функции определения преемника и часто является бесконечным, сложность выражается в терминах трех величин: b — коэффициент ветвления или максимальное количество преемников любого узла, d — глубина самого поверхностного целевого узла и т — максимальная длина любого пути в пространстве состояний.