Временная сложность обозначения Big O

Question

Мне нужно найти временную сложность некоторой функции, и я не совсем уверен, что я прав.

Давайте посмотрим:

f(int i){
    Int x = 1;
    While(x > i){
        System.out.println(x);
        x=x*2;
    }

    While(x > 2){
        x = (int) Math.pow(x,1/2);
        System.out.println(x);
    }
}

Теперь, я думаю, что первое время l oop говорит нам, что x = log (i);

, а второе l oop зависит от x, и она принимает значение x в каждой итерации:

x ^ 1/2 + x ^ 1/4 + ••• + x ^ 1 / (2 ^ k).

Предположим, что второй l oop остановится, когда x <= 2, поэтому она запустите: </p>

(Log (i)) ^ 1 / (2 ^ k) и после правил логарифма мы обнаружили, что O (loglog (n))

Answer 1

Предполагая, что первый l oop равен while(x < 1).

• Первый l oop равен log(n).
• Второй l oop равен log(log(n)).

Первый l oop является доминирующим, поэтому я бы сказал, что функция f() имеет log(n) сложность.