The Big $O$

I need to teach myself this stuff, so I'm going to make this post as a place where I can prove a bunch of elementary facts about Big O notation, (& maybe some related topics).

Starring Rarity as Roger Smith

Definition:

$f(x) = O(g(x)) \mbox{ as  } x \rightarrow \infty$ 

if and only if

$\exists \, M, x_0 \in \mathbb{R}^+ : |f(x)| \leq M|g(x)| \, \forall x > x_0$

Some basic observations:

-The equality sign here is an odd convention, because this is more of an order relation.

-This isn't a 'total ordering' when we look at all $f$ and $g$; $e^xsin(x)$ and $x^2$ are incomparable.

-There's an obvious analogue of this definition for sequences (those discrete things) and all the results discussed here apply equally to them.

Basic result(s) come after the break.

Transitivity: $f(x) = O(g(x)) \mbox{ and } g(x) = O(h(x)) \Rightarrow f(x) = O(h(x))$

$\exists \, M, N, x_0, y_0 \in \mathbb{R}^+ : |f(x)| \leq M|g(x)| \mbox{ and } |g(y)| \leq N|h(y)| \mbox{  } \,  \forall  \, x > x_0 \mbox{ and } y > y_0$

$\therefore |f(z)| \leq MN|h(z)| \, \mbox{  } \, \forall z > max(x_0,y_0)$

...and then more stuff when I get around to it...