# what is the complexity of harmonic series

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$?

• You have a mistake in your computation. the result is $O(n\log(n))$. You've missed $n$. – OmG Aug 26 '17 at 7:44
• Suppose the $j$ loop were not there at all, or were for (j = 0; j < 1; j++). Then then answer would be $\Theta(n)$. So by doing MORE work, there's no way you get $O(\log n)$. – John Hughes Aug 26 '17 at 7:44
• @OmG you mean that $\sum_{k=1}^{n-1}\lceil\frac{n}{k}\rceil$ is $O(nlog(n))$? – misha312 Aug 26 '17 at 7:47
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))$.