Here is a variation of Big-O: $\text(Little-O)$: $$ \text{Let $f, g : \mathbb{N} → \mathbb{R^{≥0}}$. We say that $g$ is little-oh of $f$, and write $g ∈ o(f)$, when:}\\ \forall c \in \mathbb{R^+}, \exists n_0 \in \mathbb{R^+}, \forall n \in \mathbb{N}, n ≥ n_0 ⇒ g(n) \leq cf(n) $$
As you can see, this is a stronger property than Big-O, in the sense that if $g \in o(f)$, then $g \in \mathcal{O(f)}$. Basically, we switch to universal quantification leading to a more powerful claim. In general, if the statement $\forall c \in \mathbb{R^+}, P(c)$ is true, then $\exists c \in \mathbb{R^+}, P(c)$ is also true. While $g \in \mathcal{O(f)}$ says (colloquially) that “it is possible to scale up $f$ so that it eventually dominates $g$,” $g \in o(f)$ says that “no matter how you scale $f$ (up or down), it will always eventually dominate $g$.” Or, in terms of rates of growth, $g \in \mathcal{O(f)}$ means that $g$ grows at most as quickly as $f$, while $g \in o(f)$ means that $g$ grows strictly slower than $f$. I hope you get my gist.
Prove the following statements about Little-o:
- Prove that for all positive real numbers $a$ and $b$, if $a<b$ then $n^a \in o(n^b)$.
- Prove that for all functions $f, g : \mathbb{N} → \mathbb{R^+}$, if $g \in o(f)$ then $f \notin \mathcal{O(g)}$.
For the first one note that $a<b$ implies $n^{a}/n^{b} = 1/n^{b-a} \to 0$.
For the second one, if $f \in O(g)$ and $g \in o(f)$ then there is some $r > 0$ such that $f(n) \leq rg(n)$ for large $n$ and for every $c > 0$ we have $g(n) \leq cf(n)$ for large $n$. So $f(n) \leq rg(n) \leq cf(n) \to 0$ as $c \to 0$ for large $n$, and hence $f=g = 0$, a contradiction.