Prove that for any positive integer $r$ and $s$ if $ r <s$ then $x^r$ is $O(x^s)$.

Question

Prove that for any positive integers $r$ and $s$ if $r <s$ then $x^r$ is $O(x^s)$.

I'm fairly new to these notations and am wondering how to do this question.

Answer 1

Let us recall what $f(x) = O(g(x))$ means [as $x \to \infty$]. It means that there exists some $C$ such that for all sufficiently large $x$ one has $|f(x)| \le C g(x)$. (Or with absolute value around the $g(x)$ but the usual convention is to only consider nonnegative $g(x)$.)

Does this work in your case? Well, of course! If $x\ge 1$ and $r < s$, then $x^{s-r}\ge 1$ and thus $x^r \le x^{r} x^{s-r} = x^s$.

Hence the claim is true with $C = 1$.

Note that I added "as $x \to \infty$." This is likely implicit in your context (discrete mathematics) but the notation is also used in other contexts, in particular in analysis with $x \to 0$, and then your claim is in fact not be true.