We have just started learning the Big O notation and have been asked to prove this statement:
$$ \forall a,b \in \mathbb{R}, a \leq b \implies n^a \in O(n^b) $$
I am really confused how to approach this problem, what are some of the steps we can take to solve such problem?
Thanks in advance :)
Are you familiar with the limit test? Take $L = \lim_{n \to \infty} \frac{n^{a}}{n^{b}}$. If $L = 0$, $n^{a} \in \omega(n^{b})$. If $0 < L < \infty$, $n^{a} \in \Theta(n^{b})$. Otherwise, $n^{a} \in o(n^{b})$, which implies $n^{a} \in O(n^{b})$.
If $u\in\Bbb R$, then $(n^u)$ is bounded iff $u\le0$.
Going back to definition, $$ n^a \in O(n^b) \iff \frac{n^a}{n^b}= n^{a-b} \text{ is bounded}\iff a\le b. $$
