Thursday, October 12, 2017

asymptotics - Help proving sumnlexlnn=xlnxx+O(lnx)

Just learning a bit about big O notation and have come across this exercise.


The notation used is nxlnn=xlnxx+O(lnx)

and I am assuming that is equivalent to xn=1lnn=xlnxx+O(lnx).



I know that x1lntdt=xlnxx+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 lnx.


Also I have no idea what tags to use, feel free to change them.

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...