0

Is $$O(1-cf(n))=O(1-f(n))$$ for any constant $c$ and any function $f$? I am afraid not. Could you tell me how to get from $$1-cf(n)$$ to $$1-f(n)?$$ Anything I can think of is $$1-cf(n)=c(1-f(n))+1-c=O(1-f(n))+1-c$$ but this does not help.

user136457
  • 2,560
  • 1
  • 22
  • 41

1 Answers1

2

If $f(x)=o(1)$, then $$O(1-cf(x))=O(1)=O(1-f(x)).$$ Otherwise, $$O(1-cf(x))=O(cf(x))=O(f(x))=O(1-f(x)).$$ UPDATE:

There is a special case: when $f(x)=O(1)$, we can have $O(1-cf(x))=o(1)$ (if the limit of $f$ is $\frac1c$). But then $1-f(x)=O(1)$.

  • So for every possible constant $c$ and every $f$ this holds?

    I have that $0<f(n)<1$, that is a bounded function, but $f(n)\notin o(1)$.

    But somehow, the first Statement looks trivial?

    Because I am little bit confused, I try to state the Problem more precisely:

    $$f(x):=Pr[Bin(n,p)\geq x]$$ Does it hold then for a constant $0<c<1$ that $$1-c f(x)=O(1-f(x))=O(Pr[Bin(n,p)<x])$$

    The Point may be, and this is what might be misleading (I'm sorry for that), that the asymptotics is in $n$ and not in $x$, $x$ is a constant.

     – user136457 Jun 06 '14 at 12:44
  • I know that a bounded function is in $O(1)$, but somehow there is more than only $O(1)$. We can say for example, that $f(n)=\frac{1}{n}$ is a bounded function and thus in $O(1)$, yes. But we can also say that $f(n)=O(\frac{1}{n})$, so I think it's reasonable to use big-O Notation even with bounded function, isn't it? – user136457 Jun 06 '14 at 12:49
  • This discussion makes little sense for a function with a finite domain. In addition, $f(x)=0$ as soon as $x>n$. –  Jun 06 '14 at 12:52
  • I am sorry, I have some typos. I tried to fix them, but it seems to be too late. We define

    $$f(n):=Pr[Bin(n,p) \geq x]$$ where $x$ is a constant. So this function does not have a finite Domain, does it?

    So my Problem is that I have $1-c f(n)$ and I want to prove that it is in $O(Pr[Bin(n,p)< x])$. Does this work?

     – user136457 Jun 06 '14 at 12:56
  • 1
    When the limit of $f$ is $1$ (the limit is $cf=c$), you have $1-cf(x)=O(1)$ while $1-f(x)=o(1)$. –  Jun 06 '14 at 13:08