6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Raphael Feb 25 '18 at 8:40
11
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ Explaining O-juggling with more O-juggling -- even though you explain the steps, I can't approve. The rigorous route is not more complicated or harder. $\endgroup$ – Raphael Feb 24 '18 at 21:42
  • 1
    $\begingroup$ What you call the rigorous route is really a pedantic route, which is mostly useful when just learning Landau notation. The correct attitude (in my opinion) is the one in the answer by ShreevatsaR. $\endgroup$ – Yuval Filmus Feb 25 '18 at 8:49
  • $\begingroup$ Since we apparently have a learner here, we seem to agree that the "pedantic" approach is the most suitable. $\endgroup$ – Raphael Feb 25 '18 at 9:00
  • 1
    $\begingroup$ Yes, for the OP it makes sense. But others that may reach this question are better off with an answer more appropriate for their stage. So it's good that there are several answers suitable for several levels of expertise. $\endgroup$ – Yuval Filmus Feb 25 '18 at 10:36
8
$\begingroup$

The real power of $O$ notation is in formulas like this. By systematically applying valid rules of manipulation, we can harness our intuition in a fully rigorous way, without much effort (such as that of dealing with explicit inequalities). (Of course, if we were allergic to $O$ notation, or not sufficiently confident about what manipulations are valid, we could immediately “translate” any $O$-containing expression we encounter into some other notation involving of sets of functions with appropriate quantifiers, but then we'd lose much of the power of $O$ notation.)

Let's look at this example in detail. In this case, we start with the expression $$\frac{2a_0(2N) \ln(2N) + O(2N)}{2a_0N\ln N+O(N)}.$$ (Presumably it has been specified earlier that in this context when we use $O()$ we are thinking of $N \to \infty$, not say $N \to 0$.)

First, to get an intuitive sense, we “THINK BIG”: for large $N$, both the numerator and denominator are dominated by their first terms, i.e. they grow as $2a_0(2N)\ln(2N)$ and $2a_0N\ln N$ respectively. As we see a common $2a_0N$ factor, we can first divide both numerator and denominator by it. Our original expression thus becomes: $$\frac{2a_0(2N) \ln(2N) + O(2N)}{2a_0N\ln N+O(N)} \stackrel{(1)}{=} \frac{2\ln(2N) + O(2N)/(2a_0N)}{\ln N + O(N)/(2a_0N)}$$ Here, the manipulation $(1)$ is simply algebra, treating the $O()$ expressions as black-boxes.

Now, in the numerator we have the term $O(2N)/(2a_0N)$. It may be obvious that this is $O(1)$, and you could indeed prove it easily, but you can also use standard manipulation rules that have been proved previously. In this case, for example, we can use a combination of:

which together give $f(n)O(g(n)) = O(f(n)g(n))$. (Recall that with equations containing $O$, all uses of the “$=$” sign are one-way: so we could not directly use $O(f(n)g(n)) = f(n)O(g(n))$ which is $(9.27)$ in the book.) So we can write $$O(2N)/(2a_0N) = \frac{1}{2a_0N} O(2N) = O\left(\frac{1}{2a_0N}2N\right) = O\left(\frac1{a_0}\right) = O(O(1)) = O(1).$$ (See $(9.25)$ in the book for $O(O(f(n))) = O(f(n))$.) Similarly, for the second term in the denominator, we get $O(N)/(2a_0N) = O(1)$. So our expression becomes: $$\frac{2\ln(2N) + O(2N)/(2a_0N)}{\ln N + O(N)/(2a_0N)} \stackrel{(2)}{=} \frac{2\ln(2N) + O(1)}{\ln N + O(1)}$$ using the manipulations above. This is the first equality in the question.


Immediately, we can write the numerator $2\ln(2N) + O(1)$ as $2\ln N + 2\ln 2 + O(1) = 2\ln N + O(1)$, again using manipulations like $c = O(1)$ and $O(1) + O(1) = O(1)$ so $c + O(1) = O(1)$. So our expression is actually: $$\frac{2\ln(2N) + O(1)}{\ln N + O(1)} \stackrel{(3)}{=} \frac{2\ln N + O(1)}{\ln N + O(1)}$$

Now, faced with a division, it may be tempting to give up $O$-manipulation and reason with inequalities. But let's have a bit more faith in mindless manipulation. :-)

We can repeat the trick of “dividing”, this time by $\ln n$, to rewrite as $$\frac{2\ln N + O(1)}{\ln N + O(1)} \stackrel{(4)}{=} \frac{2 + O(1)/\ln N}{1 + O(1)/\ln N} \stackrel{(5)}{=} \frac{2 + O\left(\frac{1}{\ln N}\right)}{1 + O\left(\frac{1}{\ln N}\right)} $$ just as before.

Finally, we can use the rule $$\frac{1}{1 + O(f(n))} = 1 + O(f(n)) \quad \text{if $f(n) = o(1)$}$$ (I can't find this one in a book right now, but it's obviously useful to have in your toolkit and you can prove it yourself using $\frac{1}{1-x} = 1 + x + x^2 + x^3 + \dots$), to rewrite the expression as $$ \begin{align} \frac{2 + O\left(\frac{1}{\ln N}\right)}{1 + O\left(\frac{1}{\ln N}\right)} &\stackrel{(6)}{=} \left(2 + O\left(\frac{1}{\ln N}\right)\right)\left(1 + O\left(\frac{1}{\ln N}\right)\right) \\ &\stackrel{(7)}{=} 2 + 2O\left(\frac{1}{\ln N}\right) + O\left(\frac{1}{\ln N}\right) + O\left(\frac{1}{\ln N}\right)O\left(\frac{1}{\ln N}\right) \\ &\stackrel{(8)}{=} 2 + O\left(\frac{1}{\ln N}\right) \end{align} $$ where I skipped a few steps in the last equation because surely you get the point by now.


Above, I just wrote everything out in detail for illustration, but in reality, after a bit of practice with valid $O$-manipulations (of course you have to be careful not to do anything that's not justified, but this is similar to when you learned during middle-school algebra not to write $(x+y)^2 = x^2 + y^2$ say), you can become comfortable and don't have to work things out so laboriously: you'll be able to write directly, say, $$ \frac{2a_0(2N) \ln(2N) + O(2N)}{2a_0N\ln N+O(N)} = \frac{2\ln N + O(1)}{\ln N+O(1)} = \frac{2 + O\left(1/\ln N\right)}{1 + O\left(1/\ln N\right)} = 2 + O\left(\frac{1}{\log N}\right) $$ pretty much as in the question. There is nothing sloppy or non-rigorous here; you're applying valid rules that have been proved.

Being able to quickly do such calculations for asymptotics is the main benefit of using $O$ notation.

$\endgroup$
5
$\begingroup$

In order to make sense of this abuse of notation, replace the original Landau terms following the placeholder semantics:

$\qquad\displaystyle f(N) = \frac{2a_0(2N) \ln(2N) + f_1(N)}{2a_0N\ln N+ f_2(N)}$

with $f_1, f_2 \in O(N)$.

Clearly (assuming that $f_2$ is non-negative),

$\begin{align*} f(n) &\leq \frac{2a_0(2N) \ln(2N) + f_1(N)}{2a_0N\ln N} \\ &= \frac{2a_0(2N) \ln(2) + 2a_0(2N) \ln(N) + f_1(N)}{2a_0N\ln N} \\ &= \frac{2 \ln(2)}{\ln(N)} + 2 + \frac{f_1(N)}{2a_0N\ln N} \\ &\leq 2 + \frac{2 \ln(2)}{\ln(N)} + \frac{c_1 N}{2a_0N\ln N} \qquad(\star)\\ &= 2 + \frac{4 a_0 \ln(2) + c_1}{2 a_0} \cdot \frac{1}{\ln N} \end{align*}$

with some $c_1 > 0$ and for all $N \geq N_1$; $c_1$ and $N_1$ come from applying the definition of $O$ at $(\star)$.

Applying the definition of $O$ again yields the claim.

$\endgroup$
  • $\begingroup$ Your first inequality doesn't follow, since we have big O in the denominator. You get an upper bound on both numerator and denominator, but this doesn't translate to an upper bound on the fraction. $\endgroup$ – Yuval Filmus Feb 24 '18 at 22:02
  • $\begingroup$ @YuvalFilmus Very true, thanks. Fixed; it even got simpler. $\endgroup$ – Raphael Feb 24 '18 at 23:06
  • $\begingroup$ The assumption that $f_2$ is nonnegative may or may not be a big one, depending on how the expression in the LHS of the question was obtained. Note that the formula in the question is true regardless of whether $f_2$ is negative or not, and the bulk of Yuval's answer is concerned with proving it without making this assumption. (With this assumption, the $$\frac{2\ln(2N)+O(1)}{\ln N+O(1)} = 2 + O\left(\frac{1}{\log N}\right)$$ part of the question essentially gets replaced by the task of proving that $$\frac{2\ln(2N) + O(1)}{\ln N} = 2 + O\left(\frac{1}{\log N}\right)$$ which is much easier.) $\endgroup$ – ShreevatsaR Feb 25 '18 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.