Ace Algorithms

Question

What is the time complexity?

i=n;
while(i>0)
{
    k=1;
    for(j=1;j<=n;j+=k)
    k++;
    i=i/2;
}

a) O(n²)

b) O(n logn)

c) O(log²n)

d) O(logn n^1/2

Comments

outer loop will run for $\log n$ times

calculating # itteration of inner loop

$j=1$

$j=1+2$

$j=1+2+3$

$j=1+2+3+4$

$j=1+2+3+4+5$

till

$1+2+3+4+...x $  becomes  $n$

$\frac{x \times (x+1)}{2} =n$

$x\approx \sqrt(n)$

hence complexity$=O(\log n  \sqrt(n))$