edited by
1,937 views

2 Answers

Best answer
2 votes
2 votes

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)

edited by
0 votes
0 votes
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})$

Related questions

0 votes
0 votes
2 answers
1
radha gogia asked Jul 7, 2018
1,547 views
foo(int n) { for(int i=0 ; i<n ;i++) for(int j=i ; j<=i*i ;j++) if(j%i==0) { for(int k=0;k<j;k++) printf("hii"); } } How to proceed here for analyzing the time complexity...
3 votes
3 votes
1 answer
3
Sanjay Sharma asked Feb 20, 2018
1,041 views
An array A is of length n has log( n) distinct numbers.What is the time complexity of sorting A by best comparison based algorithm ?