Strictly less then $o$ noation.

Question

We know that $f \in o(n)$ if $f(n)$ is strictly less than $n$, i.e., $\lim_{n}f(n)/n = 0$.

What do we mean by saying that $f(n) < o(n)$?

Does it means that $f(n) \in o(\sqrt{n})$ for example?

Answer 1

$f(n)<o(n)$ makes no sense.

Any function that grows slower than $n$ is denoted with $f(n)=o(n)$ (or $f(n)\in o(n)$).

If you want to say "grows slower than a function that grows slower than $n$", $f(n)=o(g(n))$, where $g(n)=o(n)$ or $g$ is given explictly.

Answer 2

I've never seen this notation.

What seems like a sensible interpretation would be that $f<o(g)$ if "$f$ is even smaller than $o(g)$" (or perhaps "$f=o(o((g))$"), meaning that there exists $h$ such that $f=o(h)$ and $h=o(g)$.

Except that that's a little silly, because it's not hard to see that with that definition we have $f<o(g)$ if and only if $f=o(g)$.

Edit: It's been stated that the equivalence mentioned above is false. So here's a proof:

Suppose $f=o(g)$. Wlog $g\ge0$. This says that $$\lim_{n\to\infty}\frac{|f(n)|}{g(n)}=0.$$

Since $|f(n)|/g(n)\ge0$ there exists a function $\phi(n)\ge0$ with $$\phi(n)^2=\frac{|f(n)|}{g(n)}.$$So of course $\phi(n)\to0$.

Let $h(n)=\phi(n)g(n)$. Then $$\frac{|f(n)|}{h(n)}=\frac{h(n)}{g(n)}=\phi(n),$$so $f=o(h)$ and $h=o(g)$.

Oops: It's possible that there is some division by $0$ above. Of course the values of $n$ for which we divided by $0$ don't matter; we leave it to the reader to construct a formally correct proof. (Instead of saying $f=o(g)$ means $f/g\to0$ one should say that for every $\epsilon>0$ there exists $N$ so that $|f(n)|\le \epsilon g(n)$ for all $n\ge N$.)