CODEWITHSUNDEEP
timetime-complexityasymptotic-complexity
SeasonalShot
SeasonalShot

Reputation: 2579

time complexity for the following

int i=1,s=1;
while(s<=n)
{
i++;
s=s+i;
}

time complexity for this is O(root(n)). I do not understood it how. since the series is going like 1+2+...+k . please help.

Upvotes: 0

Views: 2268

Answers (3)

Aman
Aman

Reputation: 8995

Let the loop execute x times. Now, the loop will execute as long as s is less than n.

We have :

After 1st iteration :
s = s + 1
After 2nd iteration :
s = s + 1 + 2

As it goes on for x iterations, Finally we will have

1 + 2 ... + x <= n

=> (x * (x + 1)) / 2 <= n

=> O(x^2) <= n

=> x= O (root(n))

Upvotes: 3

V-X
V-X

Reputation: 3029

s(k) = 1 + 2 + 3 + ... k = (k + 1) * k / 2

for s(k) >= n you need at least k steps. n = (k + 1) * k / 2, thus k = -1/2 +- sqrt(1 + 4 * n)/2;

you ignore constants and coeficients and O(-1/2 + sqrt(1+4n)/2) = O(sqrt(n))

Upvotes: 3

NPE
NPE

Reputation: 500427

This computes the sum s(k)=1+2+...+k and stops when s(k) > n.

Since s(k)=k*(k+1)/2, the number of iterations required for s(k) to exceed n is O(sqrt(n)).

Upvotes: 0

Related Questions