Какова временная сложность кода ниже (рекурсивная функция) по отношению к 'a'

Question

Временная сложность рекурсивного вызова

Как значение 'a' уменьшается во время рекурсивного вызова.

Это o (log a) или O (log log a) или что-то еще

int result(int a, int b)
{
 if( a %b == 0)
    return b;
 a = a % b;
 return result(b,a);
}

Answer 1

Линейное число битов, т. Е. O(log(n)).
Подсказка для доказательства: покажите, что после 2 итераций a делится не менее чем на 2