2
$\begingroup$

A follow-up question to this one basically Understanding a simplification in a theorem. If you want to see the original paper, see page 6/24 there.

We are given that $2 < n \leq M \leq n^2$. Then, the following inequality holds

$\log ( 1 + \dfrac{M}{n-2}) \geq \log n + O(1)$.

The paper goes on saying that now $\Omega (n^2)$ lower bound is obtained. How is this so? According to my understanding to actually show that, I would have to find a positive constant $c_1$, so that

$\log n + O(1) \geq c_1n^2$.

If I then divide this by $n^2$, I'll obtain

$\dfrac{\log n}{n^2} + \dfrac{O(1)}{n^2} \geq c_1$.

But as $n \to \infty$, the terms on the left side tend to 0. Therefore it is not bounded by $\Omega (n^2)$. I know I must be misunderstanding or neglecting something, what is it?

  • 0
    @Yuval: I was trying to address Gerry's comment. From what OP wrote one may come to the mistaken impression that the inequality *follows* from the condition 2 < n \leq M \leq n^2. Of course, as you showed, that inequality is not really necessary in the present discussion.2011-06-29

1 Answers 1

3

Note that $\log n + O(1)$ means $\log n + f(n)$ where |f(n)| \leq C' for some constant C' (and large enough $n$), hence it is at least $\log (Cn)$ for C = \exp(-C') > 0. Therefore $\log \left(1 + \frac{M}{n-2}\right) \geq \log (Cn).$ Exponentiating both sides, $\frac{M+n-2}{n-2} \geq Cn.$ In other words, $ M \geq Cn(n-2)-(n-2). $ Therefore $M = \Omega(n^2)$.