How is T(n) of the code O(nlog(n))? [duplicate]

Question

I dont get the part where T(n) of the second for loop is log(n). Both loops are connected by i and it is confusing.How is T(n) of the code O(nlog(n)) using fundamental product rule?

for(i = 1; i <= n; i++)
{
   for(j = 1; j <= n; j = j + i)
   {
      printf("Hi");
   }
}

Answer 1

For i=1 inner loop executes n times. For i=2 inner loop executes n/2 times and so on. The running time is T(n) = n + n/2 + n/3 + ... + n/n. This is equal to n(1 + 1/2 + 1/3 + ...+ 1/n) = nH(n) where H(n) is the nth harmonic number. H(n) ~ lg n hence the running time of O(n lg n).

Answer 2

for(i = 1; i <= n; i++)  // Executes n times
{    
    for(j = 1; j <= n; j = j + i)
    {   // This loop executes j times with j increases by rate of i
        printf(“Hi”);
    }
}

The inner loop executes n/i times for each value of i. Its running time is nxSum(n/i) for all i in [1,n]

=> O(nlogn)