2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.