Определите сложность времени, когда внутренняя l oop имеет логарифмическую c частоту внешнего цикла

Question

Я новичок в анализе сложности времени. Кто-нибудь может мне помочь с временной сложностью приведенного ниже алгоритма?

public void test(int n)
{
  int i=1;

   while(i<n)
   {
      int j=1; 
      while (j<i)
      {
         j=j*2;
      }

     i=i*2;
   }
}

external l oop будет запускать log (n) раз. Сколько раз внутренний l oop будет работать. Как мы можем вычислить частоту внутреннего l oop в терминах «n», потому что здесь она зависит от переменной «i» и будет выполнять log (i) раз.

Может кто-нибудь помочь найти временную сложность приведенного выше кода.

Answer 1

Внешний l oop будет выполняться (log n) раз.

Поскольку внутренний l oop связан с i. Таким образом, он будет работать для log1 + log2 + log3 ... log (n-1) раз для различных значений i. Решение этого выше может быть выведено в

= log (1 * 2 * 3 ... (nl). (Потому что log a * log b = log (a * b)

= log ((n-1)!). (Это (n-1) факториал)

= (n-1) log (n-1). (потому что logn! = nlogn)

SO внутренняя l oop будет иметь сложность O (nlogn).

Таким образом, сложность времени выше al go равна

logn + nlogn

, что равно O (NlogN).

Answer 2

Временная сложность данной функции составляет O(log n log n) = O(log^2 n).

Внешний l oop имеет временную сложность O (log n). Аналогично, внутренняя l oop также имеет временную сложность O(log n), поскольку значение i ограничено сверху n. Отсюда log i = O(log n).