Show that $n^a$ is in $O(n^b)$ but $n^b$ is not in $O(n^a)$, where $0 < a < b$.

Question

Let $a$ and $b$ be real numbers such that $0 < a < b$. Show that $n^a$ is in $O(n^b)$ but $n^b$ is not in $O(n^a)$.

Answer 1

The function $f(a) = x^a$ is increasing so we immediately know that $x^a = O(x^b)$ whenever $a < b$. To prove that $x^b \neq O(x^a)$ we'll suppose that it is. Then there is some constant $C$ such that, for $x$ sufficiently large \begin{equation} x^b \leq C x^a. \end{equation}

Then \begin{align} C \geq x^{b - a} \geq x^{\epsilon} \end{align} for some positive, real $\epsilon$. But the right-hand side goes to infinity so the inequality cannot hold. Therefore $x^b \neq O(x^a)$