General questions concerning asymptotic behavior

I have some difficulties understanding asymptotics in general.

Is $O(n)$ the same as $O(-n)$?

Is $O(f(n))$ the same as $O(cf(n))$ even though we know that $f(n)\leq 1$ for all $n$?

I know the general Standard rules you can find e.g. on Wikipedia, but I don't have a very good intuitive understanding of these things.

• I know now that if I want to Show an "absolute" Approximation, that I have to Show $|f-g|=o(1)$. But what about if I want to Show a relative Approximation, thus e.g. $f=g(1+o(1))$. Then I Need to Show that $|f-g|=o(g)$? Can somebody link me a good paper or a good book for this Topic of asymptotic Approximation? – user146358 May 1 '14 at 8:02

The answer to both questions is yes. The second question of course requires that $c\neq 0$, since it is obvious that $O(f(n))\neq O(0)$ for any function $f$.
For example, a function $f$ is $O(n)$, iff $|f(n)| < M|n|$ for some $M$ and large enough $n$. But a function is $O(-n)$ if $|f(n)| < M|-n|$ for some $M$, which is obviously the same.
The same goes for $O(cf(n))$, as long as $c\neq 0$. If you have a function $g\in O(f(n))$, that means that $|g(n)| < M|f(n)|$ for some $M$. But that also means that $|g(n)|< \frac{M}{|c|}|cf(n)|$, so $g\in O(cf(n))$.
• Caveat: The second in general only holds for $c \neq 0$. – Daniel Fischer Apr 30 '14 at 8:39
• And what about $f(n)$ being let's say in the range $[0.01,0.011]$, that is $min_n f(n) =0.01$ and $max_n f(n)=0.011$. Is then e.g. a constant function $g(n)=0.1$ in $O(f(n))$ as $g(n)\leq 10 f(n)$ where $10$ is a constant. But for $\sqrt{g(n)}=0.01$ so one could say that $\sqrt{g(n)}=O(f(n))$. So what about this? Does this not make sense for "too constant" functions? Or does this intuitively make sense? – user146358 Apr 30 '14 at 8:43
• What if $f$ is a probability density function (and thus we know that $f$ is bounded from above by 1). We now want to approximate $f$ by $g$. So with the things above, one could approximate $f$ by $g(n)=100$. As both functions are in $O(1)$, this is a valid Approximation, as one can write $g(n)=O(f(n))$ and $f(n)=O(g(n))$? But obviously, this is not what we want. So is it wrong to think, that an Approximation of $f$ by $g$ is valid, if $f=O(g)$ and $g=O(f)$. So do I Need that $|f-g|=o(1)$? Or how do I prove that it's a good Approximation? – user146358 Apr 30 '14 at 8:50
• Well, the big $O$ notation will tell you that all probability density functions are $O(1)$. However, that does not mean that $O(f) = O(g)$. For example, $O(1/n)\neq O(1/n^2)$, because $1/n$ is, asimptotically, larger than $1/n^2.$ – 5xum Apr 30 '14 at 8:53
• So sorry if I'm asking again and again.. But this is very difficult for me. This means that if I Show $O(f)=O(g)$ (but I can't conclude this from $f=O(1)$ and $g=O(1)$ as I've done above), then I've shown that it's a valid Approximation, and this does also imply that $|f-g|=o(1)$? By the way: your comments are very helpful! thank you. as i have too few Points, i can't give you an upvote, but I'll accept your answer.. – user146358 Apr 30 '14 at 8:57