13
$\begingroup$

I know that $f(x) = o(g(x))$ for $x \to \infty $ if (and only if) $\lim_{x \to \infty}\frac{f(x)}{g(x)}=0$ Which means than $f(x)$ has a order of growth less than that of $g(x)$.

1) I'm still confused if $x \to 0$. Because in this case $x^5 = o(x^2)$

2) Can someone list me the properties of little-o? For now, I know the following:

$f(x)*o(g(x) = o(f(x)*g(x))$

$o(f(x)) \pm o(f(x)) = o(f(x))$

Thank you!

$\endgroup$
2
  • 4
    $\begingroup$ Informally, little-o means "much smaller than". So $x^5 = o(x^2)$ as $x \to 0$ is true since $x^5$ is much smaller than $x^2$ when $x$ is close to $0$. $\endgroup$ Dec 4, 2012 at 22:01
  • 1
    $\begingroup$ thank you Antonio. I also used wolframalpha to plot various functions. Now I have a visual representation of what's happening. $\endgroup$ Dec 4, 2012 at 22:08

1 Answer 1

10
$\begingroup$

Thanks to Wikipedia** here are some properties:

  • $ o(f) + o(f) \subseteq o(f) $
  • $ o(f) o(g)\subseteq o(fg) $
  • $ o(o(f)) \subseteq o(f) $
  • $ o(f) \subseteq O(f) $

** http://en.wikipedia.org/wiki/Big_O_notation#Little-o_notation

Also, the following document may help you:

http://www.math.caltech.edu/~2010-11/1term/ma001a1/bigolittleo.pdf

$\endgroup$
3
  • $\begingroup$ thank you, I already read wikipedia before posting, but I wasn't sure if it listed also the particular cases which are usesful in most cases. My course doesn't include Big-O, so I might get confused reading the definition related to it. Can you please only tell me why the statement I wrote is true? I am unable to imagine a sort of mental representation of what's happening to the function... $\endgroup$ Dec 4, 2012 at 21:45
  • $\begingroup$ It is your welcome, the document from Caltech is more informative, go ahead with it. $\endgroup$
    – Berkheimer
    Dec 4, 2012 at 21:48
  • $\begingroup$ Ok, I'll try with it and let you know if I have problems understanding something. $\endgroup$ Dec 4, 2012 at 21:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .