Prove ∀a∈R, ∀b∈R ,[(a <= b)⇒(n^a ∈O(n^b))]

Question

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 :)

Answer 1

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

Answer 2

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