This problem:1541B - Pleasant Pairs
Editorial has the following statements:
Number of pairs(a, b) such that a*b <= 2*n is equal to
2n / 1 + 2n/2 ... where the denominator goes till 2*n.
Time complexity is said to be o(n log n), it did mention harmonic numbers, however I am having a hard time making the connection? Is this somehow in context to https://codeforces.com/blog/entry/118001 where they explain upper bound?
Any help appreciated
Let's just ignore $$$2n$$$, because we can multiply the final answer by $$$2n$$$.
And I will use another way to describe it to answer your question easier.
We can see the sum of the first $$$2n$$$ fractions of $$$\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots$$$ is approximiately $$$\log_2 2n$$$.
Then multiply this by $$$2n$$$, we get $$$2n \log_2 2n = O(n \log n)$$$.
And we can find that $$$\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}$$$ is actually $$$H_n$$$ in https://codeforces.com/blog/entry/118001.
When we say log, is it base 2? base 10? apologies, I did try simulations to calculate with ln, essentially tried a variation of ln(n), ln(2n)
I have fixed, and note that in $$$O()$$$, we don't need the base because:
and $$$c, b$$$ are constants.
Hmm, interesting. I thought that as long as the constant c, ie log(base c)(x) / log(base c)(b), is log(base b) x, which you have shown in your equation, but how does that mean that the actual base doesn't matter in O(), log2 and log10 are different things either way?
Feel free to correct me in every way possible.
Ok, actually the big O notation is not concerned in constants, and $$$\log_c b$$$ is literally a constant.