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

How did they cancel out O-terms in this fraction?

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

Problem

While reading a book about algorithms, I came across this derivation:

$$
\frac{2a_0(2N) \ln(2N) + O(2N)}{2a_0N\ln N+O(N)} =
\frac{2\ln(2N) + O(1)}{\ln N+O(1)} =
2 + O\left(\frac{1}{\log N}\right).
$$

Could somebody please explain to me how we went from the left to the right?

Solution

First, let me mention that judging from the final result, in this context $O(f(N))$ means a function $g(N)$ such that $|g(N)| \leq Cf(N)$ for some $C>0$ and all $N$.

The first step is simple: we divide both numerator and denominator by $2a_0 N$. This gives us
$$
\frac{2\ln(2N) + O(2N)/2a_0N}{\ln N + O(N)/2a_0N}.
$$
Now if $f(N) = O(N)$ then $f(N)/2a_0N = O(1)$, since $2a_0$ is a constant. This is how we get to the second fraction.

Getting to the final expression takes more work. First, notice that
$$
\frac{2\ln(2N) + O(1)}{\ln N + O(1)} = \frac{2\ln N + O(1)}{\ln N + O(1)},
$$
since $2\ln 2$ is a constant. Denote now by $B(N)$ the $O(1)$ function in the numerator, and by $C(N)$ the $O(1)$ function in the denominator. Then
$$
\frac{2\ln N + B(N)}{\ln N + C(N)} =
2 + \frac{B(N) - 2C(N)}{\ln N + C(N)} = \\
2 + [B(N) - 2C(N)] \frac{\ln N}{\ln N + C(N)} \frac{1}{\ln N} = \\
2 + [B(N) - 2C(N)] \left(1 - \frac{C(N)}{\ln N + C(N)}\right) \frac{1}{\ln N}.
$$
We need to show that the second term is $O(1/\log N)$. By definition, $|B(N)-2C(N)|$ is bounded by some constant. The same can be said about the second factor, since it tends to 1 as $N \to \infty$. Hence the entire second term is bounded in absolute value by a constant times $1/\ln N$, i.e., it is $O(1/\log N)$.

Context

StackExchange Computer Science Q#88541, answer score: 11

Revisions (0)

No revisions yet.