Asymptotics of two functions

25 Views Asked by At

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.

1

There are 1 best solutions below

5
On BEST ANSWER

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