Определите сложность времени, когда внутренняя l oop запускается вдвое больше внешней переменной l oop

Question

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

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

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

     i=i*2;
   }
}

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

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

Answer 1

Наружный l oop будет работать log(n) раз.

Скажи n = 32. Поэтому внутренний l oop будет работать для:

• n/2 для i = 1
• n/4 для i = 2
• n/8 для i = 3
• 1 для i = 31

Так что для этой геометрии c серии ее сумма будет <= 2n.

т.е. n/2 + n/4 + ..... + 1 <= 2n.

Таким образом, сложность времени вышеупомянутого алгоритма составляет

logn + 2n

, что составляет O(n).