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:\mathbf {R} \to \mathbf {R}$ and $g:\mathbf {R} \to \mathbf {R}$ be two functions, and let $a\in \mathbf {R}$ . We say that $f$ is little o of $g$ near $a$ iff for every $\epsilon >0$ there exists $\delta >0$ such that $|x-a|<\delta$ implies $|f(x)|<\epsilon |g(x)|$ .

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