### oleksg's blog

By oleksg, history, 5 weeks ago,   Comments (11)
 » 5 weeks ago, # | ← Rev. 3 →   It's n times a partial sum of [harmonic series](https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)#Partial_sums), so it's nlogn.
•  » » Oh, I didn't notice that. Thanks for the answer!
•  » » » There is also proofs for why partial sum of harmonic series is like that.
 » 5 weeks ago, # | ← Rev. 4 →   If you meant that you want to get the complexity of computing this (with floor division), you can do so in $O(\sqrt n)$ by noting that there can be at most $2 \sqrt n$ distinct terms in the sum.
•  » » No, I was specifically looking at this problem — https://codeforces.com/contest/1558/problem/B. I solved it with that complexity with a seemingly simpler solution than what the editorial offered. At least I think it was that complexity.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   Also you can also calculate the floor sum function in $O(\sqrt{n})$One of the way is to approximate $O(\sqrt{n})$ slopes in the function $y = f(x) = \left \lfloor \frac{n}{x} \right \rfloor$The other way is to split into $O(\sqrt{n})$ parts of $[A, 2A)$
•  » » yes, my favorite Dirichlet hyperbola method
 » That's n(1/2 + 1/3 + ...) 1/2 + 1/3 + ... + 1/n is the harmonic series and equals with aproximative log(n). So the complexitate will be O(nlog(n))
 » 5 weeks ago, # | ← Rev. 2 →   Here's how you can approximate that it is $nlogn$: $\frac{n}{1} + \frac{n}{2} + ... + \frac{n}{n} =$ $n(\frac{1}{1} + \frac{1}{2} +\frac{1}{3}+ \frac{1}{4} + \frac{1}{5} + \frac{1}{6}+... +\frac{1}{n} \leq$ $\leq n(\frac{1}{1} + \frac{1}{2} + \frac{1}{2} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{8} + \frac{1}{8} ... + \frac{1}{2^k} =$ $= n(\frac{1}{1} + \frac{1}{2^1} + \frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^2} + \frac{1}{2^2} + \frac{1}{2^2} + \frac{1}{2^3} + \frac{1}{2^3} ... + \frac{1}{2^k}$ $2^k \approx n \Rightarrow k \approx log_2n$ If we add all the components with the same power of 2, we get $1$. Because there are $\approx log_2n$ powers, we get that the sum is $\approx nlog_2n$
 » 5 weeks ago, # | ← Rev. 2 →   I didn't actually do this myself, but there's an interesting comment about bounding the harmonic numbers here. Jensen's inequality + some elementary calculus should do the trick (it's quite nice)You can always bound with trapezoidal rule and some calc too, if you prefer
 » galen_colin explained it here here