0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ – user146358 May 1 '14 at 8:02
1
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ Caveat: The second in general only holds for $c \neq 0$. $\endgroup$ – Daniel Fischer♦ Apr 30 '14 at 8:39
  • $\begingroup$ 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? $\endgroup$ – user146358 Apr 30 '14 at 8:43
  • $\begingroup$ 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? $\endgroup$ – user146358 Apr 30 '14 at 8:50
  • $\begingroup$ 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.$ $\endgroup$ – 5xum Apr 30 '14 at 8:53
  • $\begingroup$ 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.. $\endgroup$ – user146358 Apr 30 '14 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.