Made Easy Test Series : Algorithm

Question

for(k=1;k<(n+1);k++)
{
    for(m=1;m<(n+1);m+=k){
        x=x+1;
    }
}

What is the T.C. of the following code?

---

Is it $n^{2}$ or $n\log n$??

Comments

The inner loop runs $n$ times for $k=1$ , $\frac{n}{2}$ times for $k=2$ and so on.

Thus total number of times $x$ gets incremented will be :-

$n+\frac{n}{2}+\frac{n}{3}+.....+\frac{n}{n} = n(1+\frac{1}{2}+\frac{1}{3}+....\frac{1}{n})$

When $n$ tends to infinity , the sum $1+\frac{1}{2}+\frac{1}{3}+....\frac{1}{n}=ln(n)+C$.

Thus the complexity will be $n(ln(n)+C)=O(nln(n))=O(nLog(n))$

---

I think both are correct .

since $O(nlogn) \leqslant O(n^{2}$)

at max the inner loop runs for n/1 times.

 for next  iteration inner loop runs for n/2 times.

for next  iterations inner loop runs for n/3 times

.....

and so on until n/c=1.

$\therefore$ $\frac{n}{1} +\frac{n}{2} +\frac{n}{3} +\frac{n}{4} +....+\frac{n}{n}$

= $n( \frac{1}{1} +\frac{1}{2} +\frac{1}{3} +\frac{1}{4} +....+\frac{1}{n} )$

=$nlogn.$

---

But which one is tighter?

---

O(nlogn) is tighter.

---

so the answer must me $O(nLog(n))$ right?

---

depends on question and options

---

In that case we can take any function asymptotically greater than $O(nLog(n))$

Answer 1

for k =1 , inner for loop iterates n times.

for k=2, inner for loop iterates  n/2 times.

for k =3 , inner for loop iterates n/3 times.

......................

for k= n , inner for loop iterates n/n time.


so total = n+n/2+n/3+......n/n = n(1+1/2+1/3+....)=O(nlogn)