User:IssaRice/Little o notation: Difference between revisions

Revision as of 02:37, 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 5: / Line 5: @@
 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>
+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>?
+<div class="toccolours mw-collapsible mw-collapsed" style="overflow: auto;"> 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>.</div>