# Exponents and O notation

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!

• Well... no, of course not. If $a$ and $b$ are positive real numbers, then you can't just assume that $a = 1$ and $b = 2$. – user296602 Jan 29 '18 at 18:47
• how would u suggest to go about this then? – nickoba Jan 29 '18 at 18:58
• Your only option is to turn to the definition of Big O and show that $a < b \implies n^a \in O(n^b)$ and $a < b \implies n^b \notin O(n^a)$. – Antonio Vargas Jan 29 '18 at 19:07
• @AntonioVargas: "Your only option": don't be so pessimistic. – Yves Daoust Jan 29 '18 at 19:11
• @YvesDaoust how would you prove the last two statements in your answer if not through the definition? – Antonio Vargas Jan 29 '18 at 19:21

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$.

• how would i generalize this in terms of the definition of O notation? – nickoba Jan 29 '18 at 23:27
• @nicoba: You have to provide the proof for $1,2$ first. – Yves Daoust Jan 30 '18 at 7:12

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)$.