1
$\begingroup$

Suppose I have something like the following:

$f(x) = g(x) + O(x^n)$

And I apply a power $m$ to both sides

$f(x)^m = g(x)^m + \cdots + O(x^n)^m$

My question is whether the following is well formulated:

$O(x^n)^m = O(x^{nm})$

Thank you!

$\endgroup$
  • 1
    $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jan 9 at 18:53
  • 1
    $\begingroup$ You may want to clarify what you mean by "$O(\_)^m$" and what exactly the "$=$" is supposed to mean there. Some definitions will make that line meaningful but wrong, others meaningful and true, and yet others will result in a meaningless expression. $\endgroup$ – Raphael Jan 9 at 18:55
  • $\begingroup$ You get $f^m(x) = g^m(x) + \binom{m}{1} g^{m-1} O(x^n) + \dotsb$, which is presumably just $f^m(x) = g^m(x) + O(g^{m - 1}(x) x^n)$ (need more detail on $g$). $\endgroup$ – vonbrand Jan 14 at 17:24
1
$\begingroup$

If $f(x) = O(x^n)$ then $f(x)^m = O(x^{nm})$. Indeed, $f(x) = O(x^n)$ means that $f(x) \leq Cx^n$ for some $C>0$. Therefore $f(x)^m \leq C^mx^{nm}$, and so $f(x)^m = O(x^{nm})$.

On the other hand, it is not true that $(g(x) + h(x))^m = g(x)^m + O(h(x)^m)$. For example, suppose that $g(x) = 2$ and $h(x) = 1$. Then it is not the case that $3^m = 2^m + O(1)$.

What is true is that $(g(x) + h(x))^m = O(g(x)^m + h(x)^m)$. Indeed, if $g(x) \leq h(x)$ then $$(g(x) + h(x))^m \leq (2h(x))^m = 2^m h(x)^m = O(h(x)^m) = O(g(x)^m + h(x)^m), $$ and similarly in the other case.

(Throughout this answer, $m \geq 1$ is a constant. The first part holds for any constant $m \geq 0$.)

$\endgroup$

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.