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))**