Asymptotic analysis of a program

Question

Can you give the asymptotic analysis of this

i = 1;
k = 1;

while(k<n){
    k = k+ i;
    i = i + 1;
}

I have tried analysing but I was stuck at the inner loop

Answer 1

Let 𝑚 be the number of the iteration, then the values of 𝑘 and 𝑖 evolve as follows:

𝑚	𝑘	𝑖
0	1	1
1	1+1	2
2	1+1+2	3
3	1+1+2+3	4
4	1+1+2+3+4	5

So we see that 𝑘 is 1 + ∑^𝑚_𝑖=1 𝑖

This sum is a triangular number, and so:

      𝑘 = 1 + 𝑚(𝑚+1)/2

And if we fix 𝑚 to the total number of iterations, then:

      1 + 𝑚(𝑚-1)/2 < 𝑛 ≤ 1 + 𝑚(𝑚+1)/2.

So 𝑛 is O(𝑚²), and thus 𝑚 is O(√𝑛).

The number of iterations 𝑚 is a measure of the complexity, so it is O(√𝑛).