0

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.

user146358
  • 309
  • 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 01 '14 at 08:02

1 Answers1

1

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

5xum
  • 123,496
  • 6
  • 128
  • 204
  • Caveat: The second in general only holds for $c \neq 0$. – Daniel Fischer Apr 30 '14 at 08: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 08: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 08: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 08: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 08:57
  • I'm sorry, my writing was sloppy before. I said "if $f$ is bounded from above, then $O(f)=O(1)$" which is not true. If $f$ is bounded from above, then $O(f)\subseteq O(1)$, because any function bounded by $f$ is also bounded by a constant. – 5xum Apr 30 '14 at 09:00
  • This means that you cannot conclude that from $f\in O(1)$ and $g\in O(1)$, you have $O(f)=O(g)$. Another thing: I hope you realize that $O(f)$ is a set of functions, not a function in itself. Therefore you cannot say $f=O(g)$, but $f\in O(g).$ – 5xum Apr 30 '14 at 09:01
  • Last question, to check whether I understood your Explanation: if I want to Show for bounded $f$ and bounded $g$ that $g$ is a good Approximation of $f$, then I Need to Show that $O(f)=O(g)$ or that $|f-g|=o(1)$ (note that in the last equation I wrote a small $o$).

    Especially it doesn't help anything if I Show that $|f-g|=c$ for $c>0$? But $|f-g|=c$ would help me showing $O(f)=O(g)$ if $O(f)\neq O(1)$ and $O(g)\neq O(1)$?

     – user146358 Apr 30 '14 at 09:03
  • To prove that $g$ is an approximation of $f$, you should prove that $|f-g|\in O(h)$ for some function $h$ which has a limit of $0$. Proving that $O(f)=O(g)$ means nothing, as, for example, $O(1)=O(1000000)$ but $1$ is not an approximation of $1000000$. If, however, you prove that $|f-g|\in O(1/n)$, then you know that for large values of $n$, $f(n)$ is close to $g(n)$. – 5xum Apr 30 '14 at 09:06
  • Ok I see. Thank you very much for your help! – user146358 Apr 30 '14 at 09:08