time complexity

Question

what is T.C. of this code:

 

for(i=1;i<=n;i++)

   for(j=1;j<=n;j=j+i)

       x=x+1;

Answer 1

for (i = 1; i <= n; i++) //Outer loop
    for(j = 1; j <= n; j = j + i)   // Inner loop
        x = x + 1;

Outer loop runs $n$ times

Now for Inner loop,

$i = 1, j = 1, 2, 3,….. n $  $\text{simply } \textbf {n} \text{ times}$

$i = 2, j = 1, 3, 5,….. n $  $\text{simply } \textbf {n/2} \text{ times}$

 

so for $n$ inner loop runs

$=> n + \frac{n}{2} + \frac{n}{3}+  \dots + \frac{n}{n}$

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

$=> n\  logn$

Therefore Overall time complexity is

$T(n) =  \mathcal O(n \ logn)$

 

Comments

why again multiplied by n ???

you're already counting i, by doing when i=1, j runs... i=2, j runs... etc

---

Yes sir, My mistake

I’m correcting the answer.

---

Writing $1 + \frac{1}{2} + \frac{1}{3} + ….+ \frac{1}{n} = \log n$ is technically incorrect. It is $n^{th}$ Harmonic number i.e $H_n$ and asymptotically, $H_n \in \Theta (\ln n)$

---

yes, but that doesn't have much effect when you're interested in asymptomatic time complexities.