Error404 Blog


Main Page



Harmonic Sum analysis

When a function goes in the form of


        for(int i=1;i<=n;++i)
        {
            for(int j=2*i;j<=n;j+=i)
            cout<<(i,j);
        }
                        
$$\sum_{i=0}^n \frac{n}{i} $$ $$\implies n*\sum_{i=0}^n \frac{1}{i} $$ The summation part takes :$$O(\log{n}) $$ and total time taken is $$ O(n*\log{n}) $$

NOTE: Find why is it log(n)