retagged by
2,199 views
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; 
    } 
} 
  1. $O(n)$
  2. $O(n^2)$
  3. $O(1)$
  4. $O(\sqrt n)$
retagged by

2 Answers

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.
edited by
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))
Answer:

Related questions

0 votes
0 votes
1 answer
2
admin asked Mar 30, 2020
9,911 views
Given an undirected graph $G$ with $V$ vertices and $E$ edges, the sum of the degrees of all vertices is$E$$2E$$V$$2V$
0 votes
0 votes
1 answer
4
admin asked Mar 30, 2020
2,048 views
A path in graph $G$, which contains every vertex of $G$ and only once?Euler circuitHamiltonian pathEuler PathHamiltonian Circuit