Изучаю книгу "Алгоритмы" Рода Стивенса. В самом начале представляется классический алгоритм Евклида для нахождения НОД. Всё просто и понятно:
НОД(А, В) = НОД(В, А mod В)
Как итог - автор приводит асимптотическую сложность алгоритма, которая равна O(log(B)). И я никак не могу понять, почему это так. В самом начале автор объяснял сложность O(log(N)) на примере поиска элемента бинарного сбалансированного полного дерева. Почему у него такая сложность - я понял. А вот с НОД - никак не пойму. Разъясните пожалуйста. Спасибо.
P.S.: я относительный новичок в оценке сложности алгоритмов, поэтому буду рад очень подробному объяснению.