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!

• 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! Commented Jan 9, 2020 at 18:53
• 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. Commented Jan 9, 2020 at 18:55
• 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$). Commented Jan 14, 2020 at 17:24

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