Изменения
→КНФ в форме Хорна
Обозначим за <tex>N</tex> число вхождений переменных в формулу.
За одно повторение алгоритма мы присваиваем как минимум одной переменной значение и начинаем проделывать алгоритм для оставшихся переменных, если первый шаг не завершил алгоритм. Изначально переменных не больше <tex>N</tex>. Так как после каждого повторения алгоритма, мы уменьшаем это число хотя бы на <tex>1</tex>, то суммарно повторов алгоритма будет не больше <tex>N</tex>.
Каждый из шагов выполняется за время <tex>O(N)</tex>, а число повтора шагов алгоритма не больше <tex>N</tex>. Получается сложность <tex>O(N^2)</tex>.
}}
