What is the time complexity?

Question

 void A(int n) 
  { 
      int j = 1,i = 0; 
      while (i < n) 
      {
          i = i + j; 
          j++; 
          
      } 
      
  }

 

Answer 1

values after execution of while loop

1st time=i=1

2nd time=i=1+2

3rd       i=1+2+3

4th       i=1+2+3+4

let for ith time i=(1+2+3+......i)<n

                      =i(i+1)/2  <n

                     =i^2<n

                     i=sqrt(n)

therefore time complexity=O(sqrt  n)

Comments

Thank you for the answer. :)

Answer 2

Lets assume while loop runs x times. then time complexity is O(x) (because code inside while is O(1))

In the last iteration i = 0+1+2+3+4 ......... + x;

                              i = $\frac{x(x+1)}{2}$

           now i < n and so $x^{2} + x < 2n$ time complexity is $O(\sqrt{n})$