# User:IssaRice/Little o notation

## 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)|$. Some equivalent ways to say the same thing are:

$f$ is little o of $g$ near $a$ This is a point-free notation.
$f(x) \in o(g(x))$ as $x \to a$ This is in point notation, as the variable $x$ appears in the notation. This allows us to define functions anonymously. For example, we can say $x^2 \in o(x)$ as $x \to 0$; we didn't even name the functions. As the appearance of the symbol "$\in$" suggests, in this notation we think of $o(g(x))$ as a set, namely the set of all functions that are $o(g(x))$ as $x \to a$.
$f(x) = o(g(x))$ as $x \to a$ This is in point notation. As the equality symbol suggests, in this notation we think of f as a concrete manifestation of a function that is $o(g(x))$ near $a$. This allows us to algebraically manipulate the expression $o(g(x))$ along with all our other expressions.
$f \in o(g)$ near $a$ This is a point-free notation. As the appearance of the symbol "$\in$" suggests, in this notation we think of $o(g)$ as a set, namely the set of all functions that are $o(g)$ near $a$. In other words, $o(g) = \{f : \forall \epsilon > 0 \ \exists \delta > 0\ \forall x\ (|x-a| < \delta \implies |f(x)| < \epsilon|g(x)|)\}$
$f = o(g)$ near $a$ This is a point-free notation.

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 positive infinity (or equivalently $f(x)$ is little of $g(x)$ as $x \to \infty$) iff for every real $\epsilon > 0$ there exists a real number $M$ such that for all $x$, if $x > M$ then $|f(x)| < \epsilon|g(x)|$. We say that $f$ is little o of $g$ at negative infinity (or equivalently $f(x)$ is little of $g(x)$ as $x \to -\infty$) iff for every real $\epsilon > 0$ there exists a real number $M$ such that for all $x$, if $x < M$ then $|f(x)| < \epsilon|g(x)|$.

Exercise. Show that in the definition of little o at positive infinity, "there exists a real number $M$" can be replaced by "there exists a real number $M > 0$". Show that in the definition of little o at negative infinity, "there exists a real number $M$" can be replaced by "there exists a real number $M < 0$".

Exercise. 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$.

Exercise. If we are being a little pedantic, what is wrong with saying "$f \in o(g)$ as $x \to a$"?

Expand to see solution:

We are saying $x \to a$, but we haven't clarified what $x$ is. Instead, we are relying on the reader to assume that $x$ is an argument to $f$ and $g$.

Exercise. Interpret the meaning of $x^2 \in o(x)$.

Expand to see solution:

It depends on where $x$ is going. We want $|x^2| < \epsilon |x|$ whenever $|x-a|<\delta$, so this is only true when $a = 0$.

## Properties

Proposition. Let $f : \mathbf R \to \mathbf R$ and $g : \mathbf R \to \mathbf R$ be two functions, and suppose $g(x) \ne 0$ for all $x \in \mathbf R$. Then f is little o of g near a if and only if $\lim_{x\to a} \frac{f(x)}{g(x)} = 0$.

Proposition. transitivity

Proposition. we can replace the $<$ in the definition with $\leq$, right?

Exercise. Let $c, x_0 \in \mathbf R$ be constants. Interpret the statement "$o(c(x-x_0) + o(x-x_0)) \in o(x-x_0)$ as $x \to x_0$".

Expand to see solution:

TODO: be careful with universal vs existential quantifiers.

The statement is saying $f(x) \in o(x-x_0)$ where $f$ is some function such that $\lim_{x\to x_0} \frac{f(x)}{c(x-x_0) + o(x-x_0)} = 0$.

Because of the nested little o, we need to expand again and introduce $g$, where $g(x) \in o(x-x_0)$ so $\lim_{x\to x_0} \frac{g(x)}{x-x_0} = 0$.

Now we verify:

$\lim_{x\to x_0} \frac{f(x)}{x-x_0} = \lim \frac{f(x)}{c(x-x_0) + g(x)} \lim \frac{c(x-x_0) + g(x)}{x-x_0} = 0 \cdot (c + 0) = 0$

Could $g$ have been arbitrary? In other words, could we have said $o(c(x-x_0) + o(h(x))) \in o(x-x_0)$ for arbitrary $h(x)$? To compute the limit $\lim_{x\to x_0} \frac{f(x)}{x-x_0}$ we actually used the limit laws, which require that the right hand limit exist. This means that we needed $\lim_{x\to x_0} g(x)/h(x)$ to exist.