Complexity of a function with 1 loop

Can anyone tell me what’s the complexity of the below function? And how to calculate the complexity?

I am suspecting that it’s O(log(n)) or O(sqrt(N)). My reasoning was based on taking examples of n=4, n=8, n=16 and I found that the loop will take log(n) but I don’t think it’ll be enough since sqrt also will give the same values so I need to work on bigger values of n, so I am not sure how to approach this.

I had this function in the exam today.

void f(int n){
     int i=1;
     int j=1;
     while(j <= n){
         i += 1;
         j += i;
     }
}

Answer

The sequence j goes through is 1 3 6 10 15 21, aka the triangular numbers, aka n*(n+1)/2.

Expanded, this is ( n^2 + n ) / 2. We can ignore the scaling ( / 2) and linear ( + n) factors, which leaves us with n^2.

j grows as a n^2 polynomial, so the loop will stop after the inverse of that growth:

The time complexity is O(sqrt(n))