Big $O$ notation and Chebyshev's theorem By Chebyshev we have that, $$n\geq\frac{ap_{n}}{\log(p_{n})}$$
Where $p_{n}$ is the $n^{th}$ smallest prime and $a$ is constant. I have seen that from this, the implication that $\log(p_{n})=O(\log(n))$ and substituting back in that $p_{n}=O(n\log(n))$ however I am unsure of the steps that allow us to arrive at this.
 A: The logarithm is monotonically increasing, therefore inequalities between positive expressions are preserved when taking logarithms. Thus from Chebyshev's bound we obtain
$$\log n \geqslant \log p_n - \log \log p_n + \log a\,. \tag{$\ast$}$$
Differentiation shows that $\frac{\log x}{x}$ attains its maximum $\frac{1}{e}$ at $x = e$, hence
$$\log n \geqslant \biggl(1 - \frac{\log \log p_n}{\log p_n}\biggr)\log p_n + \log a \geqslant \biggl(1 - \frac{1}{e}\biggr)\log p_n + \log a$$
and by rearranging
$$\log p_n \leqslant \frac{e}{e-1}\biggl(\log n + \log \frac{1}{a}\biggr)$$
which yields
$$\log p_n \leqslant \frac{2e}{e-1}\log n$$
for $n \geqslant e^{1/a}$. Thus $\log p_n \in O(\log n)$. In fact, we can easily obtain the sharper $\log p_n \sim \log n$. On the one hand, $p_n \geqslant n$ and consequently $\log p_n \geqslant \log n$ is clear, and if we divide $(\ast)$ by $\log n$ (for $n \geqslant 2$) we obtain
$$1 \geqslant \biggl(1 - \frac{\log \log p_n}{\log p_n}\biggr)\frac{\log p_n}{\log n} + \frac{\log a}{\log n}\,.$$
Since $\frac{\log a}{\log n} \to 0$ and $\frac{\log \log p_n}{\log p_n} \to 0$ it follows that
$$\limsup_{n \to \infty} \frac{\log p_n}{\log n} \leqslant 1\,.$$
Since all terms of that sequence are $\geqslant 1$ this means
$$\lim_{n \to \infty} \frac{\log p_n}{\log n} = 1\,,$$
i.e. $\log p_n \sim \log n$.
Then Chebyshev's inequality yields
$$p_n \leqslant \frac{1}{a}n\log p_n \leqslant \frac{C}{a}n\log n$$
for $n \geqslant 2$ where
$$C = \max\: \biggl\{\frac{\log p_n}{\log n} : n \geqslant 2\biggr\}\,.$$
A: Since $\log(p_n) = O(\log(n))$, there exists a constant $C$ such that $\log(p_n) \leq C\cdot\log(n)$ for all $n$. So
$$ n\geq \frac{ap_n}{\log(p_n)} \geq \frac{ap_n}{C\log(n)} $$
and
$$p_n\leq \frac{C\cdot n \log(n)}{a}.$$
Thus there exists a constant $K = C/a$ such that for all $n$, $p_n \leq K\cdot n\log(n)$. So $p_n = O(n\log(n))$.
