User:IssaRice/Little o notation: Difference between revisions

Revision as of 02:50, 27 November 2018

Definition

Definition (little o near a point). Let $f : R \to R$ and $g : R \to R$ be two functions, and let $a \in R$ . We say that $f$ is little o of $g$ near $a$ iff for every $ϵ > 0$ there exists $δ > 0$ such that $| x - a | < δ$ implies $| f (x) | < ϵ | g (x) |$ . Some equivalent ways to say the same thing are:

Notation	Comments
$f$ is little o of $g$ near $a$
$f (x) \in o (g (x))$ as $x \to a$	In this notation, we think of $o (g (x))$ as a set.
$f (x) = o (g (x))$ as $x \to a$
$f \in o (g)$ near $a$
$f = o (g)$ near $a$

Definition (little o at infinity). Let $f : R \to R$ and $g : R \to R$ be two functions. We say that $f$ is little o of $g$ at infinity iff for every $ϵ > 0$ there exists $M$ such that for all $x$ , $x > M$ implies $| f (x) | < ϵ | g (x) |$ .

Can we write just $f \in o (g)$ or $f = o (g)$ or $f (x) \in o (g (x))$ or $f (x) = o (g (x))$ ?

Expand to see solution:

In general we can't because for this notation to make sense, we also need to know where the argument

x

is going. In algorithms, we have

x \to \infty

, but in analysis (e.g. in some definitions of differentiability) we have

x \to 0

.

@@ Line 3: / Line 3: @@
 Definition (little o near a point). Let <math>f : \mathbf R \to \mathbf R</math> and <math>g : \mathbf R \to \mathbf R</math> be two functions, and let <math>a \in \mathbf R</math>. We say that <math>f</math> is little o of <math>g</math> near <math>a</math> iff for every <math>\epsilon > 0</math> there exists <math>\delta > 0</math> such that <math>|x - a| < \delta</math> implies <math>|f(x)| < \epsilon|g(x)|</math>. Some equivalent ways to say the same thing are:
-* <math>f(x) \in o(g(x))</math> as <math>x \to a</math>
+{| class="wikitable"
-* <math>f(x) = o(g(x))</math> as <math>x \to a</math>
+|-
-* <math>f \in o(g)</math> near <math>a</math>
+! Notation !! Comments
+|-
+| <math>f</math> is little o of <math>g</math> near <math>a</math>
+|-
+| <math>f(x) \in o(g(x))</math> as <math>x \to a</math> || In this notation, we think of <math>o(g(x))</math> as a set.
+|-
+| <math>f(x) = o(g(x))</math> as <math>x \to a</math>
+|-
+| <math>f \in o(g)</math> near <math>a</math>
+|-
+| <math>f = o(g)</math> near <math>a</math>
+|}
 Definition (little o at infinity). Let <math>f : \mathbf R \to \mathbf R</math> and <math>g : \mathbf R \to \mathbf R</math> be two functions. We say that <math>f</math> is little o of <math>g</math> at infinity iff for every <math>\epsilon > 0</math> there exists <math>M</math> such that for all <math>x</math>, <math>x > M</math> implies <math>|f(x)| < \epsilon|g(x)|</math>.