User:IssaRice/Little o notation: Difference between revisions

Revision as of 02:29, 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) |$ .

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))$ ? 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 1: / Line 1: @@
+==Definition==
+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>.
+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>.
 Can we write just <math>f \in o(g)</math> or <math>f = o(g)</math> or <math>f(x) \in o(g(x))</math> or <math>f(x) = o(g(x))</math>? In general we can't because for this notation to make sense, we also need to know where the argument <math>x</math> is going. In algorithms, we have <math>x \to \infty</math>, but in analysis (e.g. in some definitions of differentiability) we have <math>x \to 0</math>