General questions on Landau Symbol $\mathcal{O}$

Question

Let $f\in\mathcal{O}(N)$, where I'm thinking of the definition

$$ \limsup_{N\rightarrow\infty}\bigg|\frac{f(N)}{N}\bigg|<\infty $$

I have three questions here:

First: Isn't it true, that $f\in\mathcal{O}(N)$ implies $f\in\mathcal{O}(N^k)$ for any $k>1$ by definition?

Second: Does it mean, one is generally interested in the function $g$, which is some sort of the "slowest growing" to say that $f\in\mathcal{O}(g)$? ("Just to know, which scaling is enough", so to speak?)

Third: When I read in a text, that $f\in\mathcal{O}(N)$, should I think of a function, which might not be in $\mathcal{O}(g)$ for for any $g$, which is "slower growing" than $N$? (For example $g=N^k$ for any $k<1$?)

Thanks in advance!

Answer 1

When talking about the asymptotic behaviour of a function, there is a spectrum of how precise you can be.

On one extreme, you have "$f$ is a function," which is very imprecise and tells you nothing. On the other extreme, you have "$f = f$," which is very precise but maybe isn't all that helpful. Somewhere in between, you have $f \in O(g), f \in \Theta(g), f \sim g$ and so forth.

With big-O notation, generally one of three things is happening:

1. you are giving a bound which is sufficient for the statement you are trying to prove
2. you are giving a bound which holds for a general class of functions but there may be some functions in that class for which a sharper bound holds. E.g.

$$ f(x) = f(0) + f'(0)x + O(x^2)$$

is true for all smooth functions, but if $f(x) = \cos(x)$ it's more accurately $O(x^3)$.

3. You have a specific function in mind and you are trying to provide as good an estimate that you can prove which is "nice." So not $f \in O(f)$ since that's not helpful, but maybe you'll see a statement like $f \in O(n^{1 + \epsilon})$ for all $\epsilon > 0$

Also keep in mind that big-O is just an upper bound. If you want more precise statements about the asymptotics of a function, you should give a lower bound as well. So you might say $f \in \Omega(g_1)$ and $f \in O(g_2)$. And if possible, you'll have $g_1 = g_2$ and you can say $f \in \Theta(g_1)$. But sometimes you can't prove this (yet). It's not uncommon to see statements like "$n^2 \le f(n) \le n^2 \log n$ for $n \gg 0$," in a situation where you can prove that $f \in O(n^2 \log n)$ but are not able to prove that $f \in O(n^2)$.

So to summarize, big-O depends on how precise you are able to be or how precise you need to be. If you want to be more precise, you should give a lower bound as well as an upper bound.