Time complexity of for loop-CodePudding

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 n), that is the sum of the arithmetic progression 1 till n plus n, the sum is O(n * (n 1) / 2 n) ≈ 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).