Just learning a bit about big O notation and have come across this exercise.
The notation used is $$\sum_{n\le x}{\ln{n}}=x\ln{x}-x+O(\ln{x})$$ and I am assuming that is equivalent to $$\sum_{n=1}^{x}{\ln{n}}=x\ln{x}-x+O(\ln{x}).$$
I know that $$\int_1^x{\ln{t}}\operatorname{dt}=x\ln{x}-x+1$$ so I feel like I am almost there, just not entirely sure how to make the connection, in particular exactly how the big O comes into this.
Edit: I should make it clear, I can see (I have done a quick sketch) that the summation is an 'overshoot' of the integral, and that the difference between the summation and the integral is bounded by something, but I'm not sure how to get that it is precisely $\ln{x}$.
Also I have no idea what tags to use, feel free to change them.
No comments:
Post a Comment