Time Complexity

Question

The time complexity for following piece of code is
```
i=n;
while (i>0)
{
k=1;
for (j = 1; j< = n; j + = k)
k++;
i = i/2;
}
```

Comments

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

I think time complexity is $\sqrt{n} \ * \log n$

---

Ya thanks. I got the solution

Answer 1

Outer Loop $\Rightarrow$

Now,

Inside the rectangle : j values are $\rightarrow$

$\begin{align*} j = 1,3,6,10,15,21....... n \end{align*}$

Assuming we have m terms in that series.

From above image :

• To get the $6th$ term we add $6$ to the previous term.
• So, to get the $mth$ term we add $m$ in the last increment step.
• $mth$ term is = $n$

$$\begin{align*} &\Rightarrow n = 1+2+3+4+5+6+......m \\ &\Rightarrow n = \frac{m(m+1)}{2} \\ &\Rightarrow m = O(\sqrt{n}) \end{align*}$$ 

Considering inner + outer loop   $ \Rightarrow$ $O(\sqrt{n}*\log n)$

Comments

You are correct . .  I was evaluating j=j+k at the start of loop itself ,  but it must be evaluated only after the loop body execution is done. . So I got a different series with m th term different which I mentioned above

---

Awesome explanation!!

---

Yeah nice explanation