So I'm assuming everyone's familiar with the definition of Big-O: \begin{align} ∃c \in \mathbb{R^+}, \exists n_0 \in \mathbb{R^+}, \forall n \in N, n \geq n_0 ⇒ g(n) ≤ cf(n) \end{align}
Here is a variation of this: $\text(Little-O)$: \begin{align} \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) \end{align}
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.
Can someone please prove the following challenge question for me? It would be much appreciated and I've been at it for a long time now.
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)}$.
I see that in the $2^{nd}$ part they've restricted the range of $f$ and $g$ to exclude $0$ and that we are to use only the definitions of Little-o and Big-o in order to prove both statements.