Neither a proof nor a counter-example, just first thoughts...

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)