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

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)