1
$\begingroup$

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.

  • 1
    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.2012-09-10

1 Answers 1

2

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