Exponents and O notation

Question

Prove that if $a$ or $b$ are positive real numbers and $a<b$, then $n^a \in O(n^b)$, but $n^b \notin O(n^a)$.

Could I just take $a=1$ and $b=2$ (as an example) and prove it from there? Or do I need to provide a formal proof?

Any tips would be appreciated!

Answer 1

Yes you can, provided your proof generalizes to arbitrary exponents.

---

Note that you can expresss the problem in a simpler way by the change of variable $m=n^a$, and using $r:=b/a$. The statement becomes

$$m\in O(m^r),r>1.$$

Similarly, you can rewrite the second part as

$$m\notin O(m^r),r<1.$$

These are equivalent to

$$1\in O(m^\epsilon),\\1\notin O(m^{-\epsilon})$$ for $\epsilon>0$.

Answer 2

From $a \lt b$ it follows that $\lim_{n\to\infty} |\frac{n^a}{n^b}| = 0 \lt \infty$, so $n^a \in o(n^b) \in O(n^b)$.