Тогда функция advance - тоже имеет экспоненциальную сложность?
Нет. Даже если рассматривать её рекурсивный алгоритм, она не требует более одного шага на каждый шаг рекурсии. Пример с хабра требует двух шагов. Тот факт, что второй шаг по факту вырожден, не играет качественной роли, алгоритм всё равно остаётся сложнее полиномиального. Количественно же он не требует большего объёма ресурсов.
Тонкая грань, да. Как "задача" и "метод". ;)
