Пример рекурсивного алгоритма в Java с Θ( log n)

Question

Я искал много дней, я пробовал много примеров рекурсивного алгоритма, но я не мог найти алгоритм, который имеет Θ( log n ) Продолжительность.
Знаете ли вы какой-нибудь алгоритм рекурсии в Java, которые имеют функцию T(n) = Θ( log n ), куда T(n) является функцией, выражающей количество времени, в течение которого выполняется основная операция алгоритма.
Любая помощь с очень признательна.
Спасибо!

Answer 1

В качестве одного примера рассмотрим нахождение наибольшего целочисленного показателя e целого числа m такой, что м^е | п, для некоторого целого числа n:

findBiggestExponent(int n, int m)
{
    if(n % m == 0)
        return 1 + findBiggestExponent(n/m, m);
    else
        return 0;
}

очевидно e <= log n держит. И так как рекурсивный алгоритм вычисляет e в сумме, сложность алгоритма O(log n),