oleksg's blog

By oleksg, history, 5 weeks ago, In English

Sorry if this has already been answered before, I just couldn't find the answer anywhere.

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
5 weeks ago, # |
Rev. 3   Vote: I like it +36 Vote: I do not like it

It's n times a partial sum of [harmonic series](https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)#Partial_sums), so it's nlogn.

»
5 weeks ago, # |
Rev. 4   Vote: I like it +14 Vote: I do not like it

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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it +46 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

galen_colin explained it here here