0 votes 0 votes void A(int n) { int j = 1,i = 0; while (i < n) { i = i + j; j++; } } Algorithms algorithms time-complexity + – Devshree Dubey asked Jun 7, 2016 edited Jan 10 by Hira Thakur Devshree Dubey 1.9k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
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) asu answered Jun 7, 2016 edited Jan 10 by Hira Thakur asu comment Share Follow See 1 comment See all 1 1 comment reply Devshree Dubey commented Jun 7, 2016 reply Follow Share Thank you for the answer. :) 0 votes 0 votes Please log in or register to add a comment.
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})$ dd answered Jun 7, 2016 dd comment Share Follow See all 0 reply Please log in or register to add a comment.