Big $\mathscr{O}$ notation - division operation

385 Views Asked by At

Consider that the following constant $h$ (time-step size) and $p$ as the order of convergence of some numerical method. On a source I read


$$\dfrac{\mathscr{O}(h^{p+1})}{\mathscr{O}\left(\frac{h}{2}^{p+1}\right)}=\mathscr{O}\left(h\right)\tag{1}$$


Why does the above result hold true? As far as I am concerned, if I remember correctly, it holds true that $$\mathscr{O}\left(\frac{h}{2}^{p+1}\right)=\frac{1}{2}^{p+1}\cdot\mathscr{O}\left(h^{p+1}\right)=\mathscr{O}\left(h^{p+1}\right)$$ However, I cannot realize the reason why equation $(1)$ holds true. Could you please help me understand that?

1

There are 1 best solutions below

2
On

For definition $$O(g) = \left\lbrace f:\exists C > 0, \exists U_\delta(x_0), \forall x \in U_\delta(x_0) \left(|f(x)| \leqslant C \cdot g(n) \right) \right\rbrace$$ is used notation $f(x)=O(g(x)), x\to x_0$ where under $x_0$ we understand also some $\infty$, respectively we understand neigbourhood for $x_0$. Obviously, mathematically correct record should be $f \in O(g)$, though often is used "$=$".

For simplicity let's consider positive functions. It's well known property of $O$, that for constant with respect to $x$ we can write $$ C \cdot O(g) = O(C \cdot g) = O(g) $$ where all equalities we can understand as set equalities, i.e. holds in both directions. Also it's well know properties $$ O(f) \cdot O(g) = O(f \cdot g) $$ $$g \neq 0 \Rightarrow \dfrac{O(f)}{g} = O\left( \dfrac{f}{g}\right)$$

In your example, equation (1) $\dfrac{\mathscr{O}(h^{p+1})}{\mathscr{O}\left(\frac{h}{2}^{p+1}\right)}=\mathscr{O}\left(h\right)\tag{1}$ I see following possibility: if we have $\frac{h^{p+1}}{2}$ in place of $O\left( \left( \frac{h}{2} \right)^{p+1} \right)$ and, so, on right hand then you have $O(h) = O(1)$

But in this case you second equation is not true, because now you have both functions, so $$\mathscr{O}\left(\frac{h}{2}^{p+1}\right)=\frac{1}{2}^{p+1}\cdot\mathscr{O}\left(h^{p+1}\right) \ne \mathscr{O}\left(h^{p+1}\right)$$ .