1
$\begingroup$

I'm trying to understand a theorem in a paper on page 14/24. We are given that

$$Z = (nq-1) \log \left(\frac{M+nq-1}{nq-1} \right) + M \log \left(\frac{M+nq-1}{M} \right) + \frac{1}{2} \log \left( \frac{M+nq-1}{(nq-1)M} \right) + O(1) .$$

Since $e^a > \left(1+\frac{a}{b} \right)^b$ for all $a > 0$ and positive integers $b$, the second term equals

$$\log \left(1 + \frac{nq-1}{M} \right)^M < \log e^{nq-1}$$

for all positive M and $nq-1 > 0$. This much I'm following, but then it goes on saying:

Since $0 < q < n$ and $n \leq M \leq qn^2$,

$$\dfrac{1}{2(nq-1)} \log \left( \frac{M+nq-1}{(nq-1)M} \right)\to 0 \quad \text{for } n \to \infty .$$

Where does the factor $\frac{1}{2(nq-1)}$ come from? This might even be trivial, but somehow I'm totally unable to see it.

  • 1
    Could you provide a linkt to the paper?2011-06-07
  • 0
    Given $\dfrac{1}{2(nq-1)} \log \dfrac{M+nq-1}{(nq-1)M}$, do you see why this tends to 0 as n tends to $\infty$? or do you also have a question about how to get this term?2011-06-07
  • 0
    @El G It's about getting the term mostly.2011-06-07
  • 0
    Does $\dfrac{1}{2(nq-1)} \log \dfrac{M+nq-1}{(nq-1)M} \to 0$, for $n \to \infty$ refer to the last term?2011-06-07
  • 0
    Yes, apparently so.2011-06-07
  • 0
    @Raskolnikov Sure, it's here [link](http://homepages.cwi.nl/~paulv/papers/sorting.pdf) (page 14/24 of the pdf).2011-06-08
  • 0
    maybe the author wants only to show that $2(nq-1)$ tends to $\infty$ faster than $\log \frac{M + nq -1}{(nq-1)M}$.2011-06-08

1 Answers 1

1

OK, thanks to the paper, I figured it out. What they do is rewrite

$$Z = (nq-1) \log \dfrac{M+nq-1}{nq-1} + M \log \dfrac{M+nq-1}{M} + \dfrac{1}{2} \log \dfrac{M+nq-1}{(nq-1)M} + O(1)$$

with their formula for the second term

$$M\log\left(1 + \dfrac{nq-1}{M}\right) < (nq-1)\log e$$

which gives

$$Z < (nq-1) \log \dfrac{M+nq-1}{nq-1} + (nq-1)\log e + \dfrac{1}{2} \log \dfrac{M+nq-1}{(nq-1)M} + O(1)$$

Of course, it has become an inequality, particularly an upper bound for $Z$. Now separate out the factor $(np-1)$ and you'll get

$$Z < (nq-1) \left( \log \dfrac{M+nq-1}{nq-1} + \log e + \dfrac{1}{2(nq-1)} \log \dfrac{M+nq-1}{(nq-1)M} + O\left(\frac{1}{nq-1}\right) \right)$$

Now, see the third term is exactly what they are computing the limit of. Since that goes to zero, and the $O\left(\frac{1}{nq-1}\right)$ term does as well, you get the end result

$$Z < (nq-1)\left( \log \dfrac{M+nq-1}{nq-1} + \log e \right) \; .$$

  • 0
    Ahh, I see. Thanks a lot!2011-06-08