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!
3
-
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$– RaphaelCommented Jan 9, 2020 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$– RaphaelCommented Jan 9, 2020 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$– vonbrandCommented Jan 14, 2020 at 17:24
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.)
answered Jan 9, 2020 at 20:19