Is it O(n) or O(n*n)?

The loop runs approximately n*n times but the loop variable is only one.

I'm confused whether it's O(n) algorithm I think it should be O(n*n) but gfg says it's O(n)

Can anybody help me with the answer??

int j=0;
for(int i=1; i<=n; )
{
   if(j<i)
   {
     j  ;
     continue;
   }

   if(j==i)
   {
     i  ;
     j=0;
   }
}

CodePudding user response：

This is O(1 2 ... n), that is the arithmetic progression, the sum is O(n * (n 1) / 2) ≈ O(n²).

CodePudding user response：

I think this loop runs 1 2 ... n times because j needs to be incremented i - 1 times as i grows, and i grows n times. That gives a time complexity of O(n^2).