2

I'm looking at the following excerpt from The Probabilistic Method by Alon and Spencer:

enter image description here

I'm probably missing something very obvious, but I don't see how $f(n) < \log_2 n + \log_2 \log_2 n + O(1)$ follows from $2^{f(n)} < nf(n)$. Clearly when you take log of both sides you get $f(n) < \log_2 n + \log_2f(n)$. And then it seems they must be using our lower bound, $f(n) \ge 1 + \left\lfloor \log_2 n \right\rfloor$ somehow. I don't get how the lower bound is useful though as it doesn't seem we can just substitute it in. E.g., if $f(n)$ takes a value much greater than $1 + \left\lfloor \log_2 n \right\rfloor$, our upper bound will be artificially low.

kanso37
  • 358

1 Answers1

1

We know that $0 < f(n) - \log_2 n < \log_2 f(n)$.

Let $x_n := f(n) - \log_2 n - \log_2 \log_2 n$.

We can rewrite the first equation as $$0 < \log_2\log_2 n + x_n < \log_2 \left(\log_2 n + \log_2 \log_2 n + x_n\right) $$

The right handside can be rewritten by noting that if $a \neq 0$, $\log(a + b) = \log(a(1 + b/a)) = \log a + \log(1 + b/a)$:

$$\log_2\log_2 n + x_n < \log_2 \log_2 n +\log_2\left(1 + \frac{\log_2\log_2 n}{\log_2 n} + \frac{x_n}{\log_2 n}\right)$$

As $n \to \infty$, $\frac{\log_2\log_2 n}{\log_2 n} \to 0$, so effectively for large $n$ we have for very small $\epsilon$ $$x_n < \log_2\left(1 + \frac{x_n}{\log_2 n}\right) + \epsilon,$$

which can only happen if $x_n$ is either very small or negative.

In any case, since $x_n$ is bounded for large $n$, it follows that there must be a constant $C$ such that $x_n < C$. This shows that $f(n) < \log_2 n + \log_2 \log_2 n + O(1)$.

Pedro M.
  • 3,061
  • 18
  • 19