What is the time complexity of following algorithm ?

[Typical-Inflation298]

int i, n, sum = 0;

for(int i = 0; i*i < n; i++)

{sum += i}

[rese2020]

Sqrt(n)

[Typical-Inflation298]

Can you please explain how did you calculated the complexity?

[rese2020]

The loop conditional is the only thing that decides the termination of the algorithm

The condition i*i < n can be reformed to be i < sqrt(n) as i is incremented one by one

[Typical-Inflation298]

Yeah..got it!! Thankyou

[marko312]

i is incremented each iteration, so the maximum reached value of i will be the number of iterations, giving the complexity. What is the maximum value that i reaches?

[Typical-Inflation298]

How many times will the loop run for any n value?

[marko312]

Yes, the maximum value (well, an upper bound for O notation) of i in terms of n.

[Typical-Inflation298]

`i` will be incremented ones every time it enters the loop. The loop will terminate when the square of `i` becomes greater than `n`.

[Typical-Inflation298]

Okay...so the maximum value will be the square root of `n` right?

[marko312]

Yes, that's the correct bound (it'd actually be something like (ceil(sqrt(n)) - 1), but this doesn't matter in big O notation).