Dark Mode

419 views

1 vote

Best answer

Initially i = 0 , j = 1

After 1st iteration , i = i + j = 1 , j = 1 + 1 = 2 [ as 'j' is incremented ]

After 2nd iteration , i = i + j = 1 + 2 = 3 , j = 2 + 1 = 3

After 3rd iteration , i = i + j = 3 + 3 = 6 , j = 4

So we can see

after xth iteration , we get i = sum of x consecutive terms starting from 1

= x(x+1)/2

Also i keeps on incrementing till the condition : i < n is true..

Hence , to find the terminating condition we equate i to n..

So ,

x(x+1)/2 = n

==> x^{2} = n [ As to find asymptotic bound , we need to consider dominating terms only and x^{2} is dominating here as it is the highest power term , Also constants are ignored..]

==> x = sqrt(n)

**Hence time complexity = O(sqrt(n))**