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:

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:\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)|$.

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)\neq 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:

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.