确定内部回路具有外部回路对数频率时的时间复杂度

Question

我是分析时间复杂度的新手。有人可以帮助我解决以下算法的时间复杂度吗？

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

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

     i=i*2;
   }
}

外循环将运行log（n）次。内循环将运行多少次。我们如何计算内部频率循环以“ n”表示，因为这里它取决于变量“ i”，并且将运行log（i）次。

有人可以帮忙找出上述代码的时间复杂度。

Answer 1

给定函数的时间复杂度为O(log n log n) = O(log^2 n)。

外部循环的时间复杂度为O（log n）。类似地，内部循环也具有时间复杂度O(log n)，因为i的值在上方受n限制。因此，log i = O(log n)。