Измените данный код, чтобы он соответствовал временной сложности O (n * log (n))

Question

текущая временная сложность равна θ (n ² .log (n)), и мне нужно изменить проверку в For l oop, чтобы временная сложность была: θ (n.log (п)). Предлагаемое решение - i*i<n, но я не могу понять почему.

int f2(int n)
{
     int x, y, z=0, i;
     for (x=n, i=0; i<n; i++, x*=n)
     {
          y=x;
          while (y>1)
              y/=3;
          z+=y;
     }
     return z;
 }

Answer 1

Итак, я нашел причину, по которой решение условия проверки - i*i<n. Временная сложность текущего кода складывается из следующих журналов: log(n)+log(n^2)+log(n^3)+...+log(n^n) = log(n)*(1+2+3+...+n)= θ (n ² .log (n)). Если я изменю формулу суммы так, чтобы сумма увеличилась до sqrt(n), результатом будет ((sqrt(n))^2 = n). и я получу требуемую временную сложность: θ (n * log (n). и код будет:

int f2(int n)
{
     int x, y, z=0, i;
     for (x=n, i=0; i*i<n; i++, x*=n)
     {
          y=x;
          while (y>1)
              y/=3;
          z+=y;
     }
     return z;
 }