Little-O: $\forall c \in \mathbb{R^+}, \exists n_0 \in \mathbb{R^+}, \forall n \in \mathbb{N}, n ≥ n_0 ⇒ g(n) \leq cf(n)$

Question

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:

1. Prove that for all positive real numbers $a$ and $b$, if $a<b$ then $n^a \in o(n^b)$.
2. 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.

Answer 1

For positive functions $f,g\colon \mathbb{N} \to \mathbb{R}_+$, you can show that

• $f(n) = o(g(n))$ iff $\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0$.
• $f(n) = O(g(n))$ iff $\limsup_{n\to\infty} \frac{f(n)}{g(n)} < \infty$.

Using this, it is not hard to prove the two statements. Once you have done that, try translating your proofs to the definitions you were given.