Большая сложность внутренних циклов

Question

Большой O внешнего цикла - O (n), и я думаю, что второй внутренний цикл большого O - это log (n), но я не могу понять, большой O третьего внутреннего цикла

for(i=0;i<n;i+=2)
{
    for(j=1;j<i*i;j*=3)
    {
       for(k=2;k*k<=n;k++){}
    }
}

Answer 1

Внешний цикл выполняется n-2 раза, что усложняет O (n).Во втором цикле значение j увеличивается в степени от 3 до i * i, что равно log3 (i * i).поэтому для обоих объединенных циклов это ∑ _{i = 1} ^n-2 log3 (i), что равно log3 (n!) или просто n * log (n) какты упомянул.Самый внутренний цикл выполняется sqrt (n) раз, что составляет общую сложность O (n * log (n) * sqrt (n))