what is the complexity of harmonic series

Question

I try to evaluate the complexity of the following pseudo code:

S=0;
for (i=1; i<n; i++)
  for (j=0; j<n; j+=i)
    S=S+1;

At first it seems pretty straight forward:

First for loop - $n$

and what about the second one? $\sum_{k=1}^{n-1}(\lceil\frac{n}{k}\rceil+1) + \sum_{k=1}^{n-1}\lceil\frac{n}{k}\rceil$

so the answer should be something like : $n+n-1+\sum_{k=1}^{n-1}\lceil\frac{n}{k}\rceil + \sum_{k=1}^{n-1}\lceil\frac{n}{k}\rceil$

now I think that $\sum_{k=1}^{n-1}\frac{n}{k}$ is a harmonic series so $\sum_{k=1}^{n-1}\frac{n}{k}=O(nlog(n))$ (this is only the harmoic part without the rest is it correct??)

But what can I do if it is $\sum_{k=1}^{n-1}\lceil\frac{n}{k}\rceil$?

Please help me figure it out.

Answer 1

You have a mistake in your computation. the result is $O(n\log(n))$. You've missed $n$ in your final result.

Also, for the complexity case you can ignore the ceil function. Because at most the difference between each item $\lceil \frac{n}{k}\rceil$ and $\frac{n}{k}$ is $1$ , then you can ignore it for the complexity case. it means it does not change the complexity, as it would be $O(n\log(n) + n) = O(n\log(n))$.