2 votes 2 votes What is the running time of the following function (specified as a function of the input value)? void Function(int n){ int i=1; int s=1; while(s<=n){ i++; s=s+i; } } $O(n)$ $O(n^2)$ $O(1)$ $O(\sqrt n)$ Algorithms nielit2017july-scientistb-it algorithms time-complexity asymptotic-notation + – admin asked Mar 30, 2020 retagged Aug 23, 2020 by Lakshman Bhaiya admin 2.2k views answer comment Share Follow See 1 comment See all 1 1 comment reply Sanandan commented Sep 11, 2020 reply Follow Share option D) O(n^1/2) is correct 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes At each step we are increasing S by i, where i indicates the number of iterations we had till now. Here S is sum of first i natural number. $i(i+1)/2 = n \implies i = \sqrt{n}$ So, D is correct. smsubham answered Mar 30, 2020 edited Oct 2, 2020 by Lakshman Bhaiya smsubham comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes i=1,2,3...k s=1,3,6,...>n here we can obseve that each value in s in equal to sum of i's upto corresponding i value 3=1+2 6=1+2+3 so n<k(k+1)/2 n<k^2 answer is O(sqrt(n)) rahul_6 answered Jun 10, 2020 rahul_6 comment Share Follow See all 0 reply Please log in or register to add a comment.