Calicut Gate Academy Test Series | DAA Time complexity Q2

Question

Complexity of the following snippet is 

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

Comments

your inner loop has some error i guess it shud be j<=n and not i<=n

---

corrected :)

Answer 1

See we analyse this as :

When i = 1 , j is incremented in steps of 1 as j = j + i and i = 1 for 1st iteration..

So j as clear from the program runs from 1 to n and increment is done by 1 in each inner loop..

So number of times the inner loop runs = n for i = 1

Similarly for i = 2 , inner loop runs n/2 times as j = j + 2 for i = 2..

Similarly for i = 3 , inner loop runs n/3 times as j = j + 3 for i = 3..

and so on till i = n-1

So time complexity = n + n/2 + n/3 + n/4...................

                             = n(1 + 1/2 + 1/3 ..........)

Now the series written inside the brackets is a harmonic series ..So addition formula is not there..However we can approximate by doing the integration of 1/n w.r.t n which gives us logn..

So time complexity  = O(nlogn)

Answer 2

for a general i-th iteration, the inner loop runs O(n/i)

O(n + n/1 + n/2 + ..... + n/n) = O((n)(1 + 1 + 1/2 + .... +1/n)) = O(nlogn)