Since , we have the right upper bound.
There is a matching lower bound: for , and, using (consequence of Stirling formula), we obtain . Therefore, with the upper bound:
However, I suspect that can fluctuate when is between two successive points of that would be "far away from each other". Allowing for arbitrary seems too weak an assumption to me: it can be an incredibly "hollow" sequence...
Can you prove the theorem for ? Or for any other sequence that grows faster than linearly? (I would be curious of what method you would use)