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!

  • $\begingroup$ 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$. $\endgroup$ – user296602 Jan 29 '18 at 18:47
  • $\begingroup$ how would u suggest to go about this then? $\endgroup$ – nickoba Jan 29 '18 at 18:58
  • $\begingroup$ 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)$. $\endgroup$ – Antonio Vargas Jan 29 '18 at 19:07
  • $\begingroup$ @AntonioVargas: "Your only option": don't be so pessimistic. $\endgroup$ – Yves Daoust Jan 29 '18 at 19:11
  • $\begingroup$ @YvesDaoust how would you prove the last two statements in your answer if not through the definition? $\endgroup$ – 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$.

  • $\begingroup$ how would i generalize this in terms of the definition of O notation? $\endgroup$ – nickoba Jan 29 '18 at 23:27
  • $\begingroup$ @nicoba: You have to provide the proof for $1,2$ first. $\endgroup$ – 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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.