嵌套循环的C-时间复杂度

Question

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

我的困惑是-

如果我把n+(n^2-1)*O(1)写成n+O(1)+O(1)+........+O(1)，那么我可以忽略低阶项，复杂性将是O(n)，但是另一个推理可以是一个常数的工作量正在做n^2次，所以时间复杂性应该是O(n^2)

在这个问题中也发生了类似的事情-带有if语句的嵌套循环的时间复杂度O(N):O(N^4)？

  j=0;
    while(j<n)
    {
        j++;
    }

Answer 1

时间复杂度为O(n^2)。

外部循环只运行一次，因此可以忽略它。中间的循环运行n*n次，其中只有第一次迭代需要O(n)步骤，其余的是O(1)，因为J将是n。

所以它是O(n^2+n)=O(n^2)。