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.

  • 0
    $f(x)$ might well be $O(f(x)-x)$. So it is good that you don't manage to prove it.2012-09-10
  • 0
    @Fabian any handy counterxample to show me that?2012-09-10
  • 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