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

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");
   }
}

Yes j=j+i, How do we proceed with this. How to calculate T(n) for dependent loops? — Hari, Oct 05 '14 at 11:51
Much similar question: http://stackoverflow.com/questions/18863422/asymptotic-analysis — Grzegorz Szpetkowski, Oct 05 '14 at 12:02

score 5 · Accepted Answer · answered Oct 05 '14 at 11:55

5

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).

answered Oct 05 '14 at 11:55

mrk

3,061
1
29
34

Awesome!! But can u help me out how to do the problem using product rule of finding T(n)? @saadtaame – Hari Oct 05 '14 at 11:56
1

That's a product! The second factor is just a bit different than what you are used to. If inner loop executed `m` times for example you would write `m + m + ... + m`, `m` appears `n` times. Makes sense? – mrk Oct 05 '14 at 12:06

score 2 · Answer 2 · answered Oct 05 '14 at 11:53

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)

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

2 Answers2