Comparison and properties of big O notation

40 Views Asked by At

Comparison

Say I have a function $f(x)$, and I expand it using the Taylor series, up to the first and the second degree. Then I will have two approximations $f_1(x),f_2(x)$, with errors $\mathcal{O}(h^2),\mathcal{O}(h^3)$ respectively.

Can we compare $\mathcal{O}(h^2)$ with $\mathcal{O}(h^3)$? I think here we can as $h\rightarrow0$, therefore $\mathcal{O}(h^2)$ decreases more slowly than $\mathcal{O}(h^3)$. However in general I think we can't as the comparison depends on whether $h\rightarrow0$ or $h\rightarrow \infty$. Is this idea correct?


Property

Now, let's have another function $g(x)\in\mathcal{O}(h^2)$, what's the result of $g-f_1$? It's $\mathcal{O}(h^2)$ generally, and $0$ if $g=f_1$ right?

Also can I claim that $g(x)\in\mathcal{O}(h),g(x)\notin\mathcal{O}(h^3)$, because I think $\mathcal{O}(h)$ is less strict than $\mathcal{O}(h^2)$ in terms of errors??

1

There are 1 best solutions below

2
On BEST ANSWER

Let me consider your claims one by one. I will avoid using too short notations, as I believe it can lead you to some errors.

So, you started from a function $f : x \mapsto f(x)$, say regular enough, you chose some reference fixed point $x_0$, and wrote two Taylors expansions of $f$ near $x_0$, namely: $$ f(x_0+h) = (f(x_0) + h f'(x_0)) + \mathcal{O}_{h \to 0}(h^2) $$ and $$ f(x_0+h) = \left(f(x_0) + h f'(x_0) + \frac{h^2}{2} f''(x_0)\right) + \mathcal{O}_{h \to 0}(h^3) $$ Then you introduced $f_1(h) := f(x_0) + h f'(x_0)$ (which is now a function of $h$, but this function $f_1$ itself depends on $x_0$), and $f_2(h) = f_1(h) + h^2/2 f''(x_0)$.

Now let me turn to your questions.

  1. About comparing $\mathcal{O}$s. You should avoid omitting the limit under which these $\mathcal{O}$s are considered. Either you write it explicitly in subscript, or in full letters after the equalities. This makes it clear that here, indeed, if $g(h) = \mathcal{O}_{h\to0}(h^3)$, then $g(h) = \mathcal{O}_{h\to0}(h^2)$. Of course, it would be the other way around when $h \to \infty$.

  2. About summing $\mathcal{O}$s. If $g_1(h) = \mathcal{O}_{h\to0}(h^r)$ and $g_2(h)=\mathcal{O}_{h\to0}(h^s)$, indeed $(g_1+g_2)(h) = \mathcal{O}_{h\to0}(h^{\min \{r,s\}})$, i.e. the worst estimate holds, but it could happen that it is arbitrarily better, or even $0$ as you mention. For example, if $g_1(h) = h = \mathcal{O}_{h\to0}(h)$ and $g_2(h) = -h + h^3 = \mathcal{O}_{h\to0}(h)$, then $(g_1+g_2)(h) = h^3 = \mathcal{O}_{h\to0}(h^3)$.

  3. About excluding $\mathcal{O}$s. Sure, sometimes, you will handle functions such that $g(h) = \mathcal{O}_{h\to0}(h)$ and $g(h) \neq \mathcal{O}_{h\to0}(h^3)$. But the mere statement $g(h) = \mathcal{O}_{h\to0}(h)$ does not entail the second one. For example $g(h) := h^3$ is $\mathcal{O}_{h\to0}(h)$ and $\mathcal{O}_{h\to0}(h^3)$ (both at the same time).