Proving that $f(x)$ is not $O(\log f(x))$

Question

I tried to prove (by contradiction) that, given a positive function $f(x)$, it is not $O(\log(f(x))$ (in this case, log denotes the base 2 logarithm).

The problem is that I do not know anything about the behaviour of the function (and therefore nothing about its log), so I can't really know how to proceed.

I have the same difficulties when trying to prove that $f(x)$ is not $O(f(x)-x)$.

I might even be wrong, but I have hardly an idea how to start proving/disproving these thins, and some help is more than appreciated.

$f(x)$ might well be $O(f(x)-x)$. So it is good that you don't manage to prove it. — Fabian, Sep 10 '12 at 19:26
big $O$ relates to largest bounds, so if we take $f(x)=x^2$ (or any function with faster than linear growth), we get $O(f(x))=O(f(x)-x)=O(x^2)$, since the $x^2$ term dominates in both cases. — Robert Mastragostino, Sep 10 '12 at 19:58

score 2 · Answer 1 · answered Sep 10 '12 at 18:51

Suppose that $f(x)$ is $O(\log f(x))$; this means that there are positive constants $x_0$ and $C$ such that $|f(x)|\le C|\log f(x)|$ for all $x\ge x_0$, and since $f$ is positive, we can drop the first absolute values: $f(x)\le C|\log f(x)|$ for all $x\ge x_0$. We can also divide by $f(x)$ and $C$:

$$\frac{|\log f(x)|}{f(x)}\ge\frac1C\tag{1}$$

for all $x\ge x_0$. You know that $\lim_{x\to\infty}\frac{\log x}x=0$, so $(1)$ is impossible if $f(x)$ is unbounded. Can you find a bounded positive function for which $(1)$ is satisfied? That would give you a counterexample to the conjecture that $f(x)$ is never $O(\log f(x))$.

Proving that $f(x)$ is not $O(\log f(x))$

1 Answers1