If a function is "little oh of something", does it mean that the runtime of that function is strictly less than that?

Question

I'm currently studying little oh notation. I found it a bit confusing initially, but I think I've got it now and I'd just like to check my understanding.

So I found the question: $f(n) = 2 n^2 + 4 n \log( n^4 )$

And the correct runtime for this is: $f(n)$ is $\Omega(n^3)$, and $f(n)$ is $o(n^3)$.

So from my understanding of little o, it basically says that a function grows at a definitely better rate than what is given in the little o, so in that example, it is o(n^3) which says that the function grows at a definitely better time complexity than n^3 , so it cannot be n^3 (since little o definition is f(n) < o(g(n)) but it could be n^2, n, log n etc. so if I was to say that that function is o(n^2) it'd be incorrect because it would assume that the function grows better than a quadratic, which is incorrect due to the n^2 within the function.

Answer 1

That is not the standard definition of little o

Try instead (from Wikipedia):

$f(x)=o(g(x))\text{ as }x\to\infty$

if for every positive constant $\varepsilon$ there exists a constant $N$

such that $|f(x)|\leq\varepsilon g(x)\text{ for all }x\geq N~.$

It is true here that $f(n)=2 n^2 + 4 n \log( n^4 ) = o(n^3)$ as $n\to\infty$ and you can prove it by saying that $f(n) \lt 11 n^2$ for all positive $n$ and so $f(n) \lt \varepsilon n^3$ if $n \gt \frac{11}{\varepsilon}$.

Answer 2

$f(n) = o(n^3)$ means $|f(n)|/n^3 \to 0$ as $n \to \infty$.

You are correct that, for your example, $f(n) \ne o(n^2)$ because $|f(n)|/n^2 \not\to 0$ (the limit is $2$). Note however that your $f$ is not only $o(n^3)$ but also $o(n^{2.5})$ and $o(n^{2.0000001})$.

In general, you can think of $f(n) = o(g(n))$ as "$f$ growing at a rate strictly slower than $g$" in the sense that $|f(n)/g(n)| \to 0$ as $n \to \infty$.