# What is the correct time complexity of the following code

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?

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

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.