HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Big O notation: removing big O from denominator

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
removingbigdenominatornotationfrom

Problem

In A First Course in the Numerical Analysis of Differential Equations (page 26) Arieh Iserles gives the following derivation:
\begin{equation}
\frac{\rho(w)}{\ln(w)}=\frac{\xi+\xi^2}{\xi-\frac{1}{2}\xi^2+\frac{1}{3}\xi^3+\mathcal{O}(\xi^{4})}=\frac{1+\xi}{1-\frac{1}{2}\xi+\frac{1}{3}\xi^2}+\mathcal{O(\xi^3)}
\end{equation}
where $\xi=w-1$, $\rho(w)=w^2-w$ and $\xi\to 0$. I understand the expansion of the logarithm in the denominator, but how does the second step work? I have no idea how this big O is removed from the denominator. Can anyone explain this please?

Solution

Let's start out simple:

$${1 \over 1 + x} = 1 - x + x^2 - \cdots$$

so it follows that

$${1 \over 1 + O(x)} = 1 + O(x)$$

as $x \to 0$.

(Background: I interpret $O(x)$ as representing any function $f(x)$ where $|f(x)|$ is asymptotically no larger than $x$, i.e., there exist constants $c_0,x_0$ such that $|f(x)| \le c_0 |x|$ for all $-x_0 \le x \le x_0$. This is the likely meaning of big-O notation in this context, where we are concerned about the asymptotic behavior as $x \to 0$ and where values can be either positive and negative. If it looks a little different from what you are used to in computer science, that's because in CS we most commonly deal with the situation where we have a function $f(n)$ where $n \to \infty$ and where all values are positive, so the definition looks a bit different in that context.)

Now suppose $v=O(1)$, and take a more complex expression:

$${1 \over 1 + v + O(x)} = {1 \over 1+v} \cdot {1 \over 1 + O(x)} = {1 \over 1+v}(1 + O(x)) = {1 \over 1+v} + O(x),$$

where I have used that $v \cdot O(x)=O(x)$, etc.

Finally, if $u=O(1)$, we can multiply both sides by $1+u$ to see that

$${1+u \over 1+v+O(x)} = {1+u \over 1+v} + O(x).$$

Now plug in $x=\xi^3$ and $u = \xi$ and $v = -\frac12 \xi + \frac13 \xi^2$, and we obtain

$$
\frac{1+\xi}{1-\frac{1}{2}\xi+\frac{1}{3}\xi^2+\mathcal{O}(\xi^{3})}=\frac{1+\xi}{1-\frac{1}{2}\xi+\frac{1}{3}\xi^2}+\mathcal{O(\xi^3)}
$$

which is the step of the derivation you are asking about.

Context

StackExchange Computer Science Q#96145, answer score: 2

Revisions (0)

No revisions yet.