What is the correct time complexity of the following code

Question

I was wondering what is the correct time complexity expressed in terms of big O on this type of loop:

for(i=1;i<=n;i++)
    for(int j=1;j*i<=n;j++)
        // O(1) code here

The inner loops will make $n + \frac{n}{2} + \frac{n}{3} + \dots + \frac{n}{n}$. I know that this type of formula is $O(n \log n)$, so is this the correct time complexity on this piece of code?

Answer 1

$$n+\frac{n}{2}+\cdots +\frac{n}{n}$$

$$= n(1+\frac{1}{2}+\cdots +\frac{1}{n})$$

Now it is a well-known fact that $1+\frac{1}{2}+\cdots +\frac{1}{n} \le c \log n$, where $c$ is some constant.

$$\le cn(\log n)$$

So the overall Runtime is $\mathcal{O}{(n \log n)}$.

Answer 2

The number of times that the body of the inner loop runs is exactly $$ T(n) = \sum_{i=1}^n \left\lfloor \frac{n}{i} \right\rfloor. $$ This is sequence A006218 in OEIS, where it is stated that $$ T(n) = n(\log n + 2\gamma - 1) + \tilde O(n^{131/416}). $$ The exact magnitude of the error term isn't known, but it cannot be reduced below $\tilde O(n^{1/4})$.

For more references, see the Wikipedia article on Dirichlet's divisor problem.