Say we have two functions: $f(n) = n$ and $g(n) = 2n$.
$$\lim_{n\to\infty} \frac{f(n)}{g(n)} = \lim_{n\to\infty} \frac{n}{2n} = \lim_{n\to\infty} \frac{1}{2} = \frac{1}{2}$$
Therefore, according to the answer here, function $g(n)$ grows faster than $f(n)$ because: $$0 \leq \lim_{n\to\infty} \frac{f(n)}{g(n)} < 1$$
But with big O notation: $f(n) = O(n)$ and $g(n) = O(n)$
Which means that both functions grow at the same rate (in an apparently different magnitude).
I realise that this is only happening because the coefficient of the largest term is ignored with big O notation but I want to know if you can use limits to give information about the big O notation of a function and vice versa because I find some of this terminology and these concepts hard to differentiate.
Thanks.
Best Answer
Definition: $f=O(g)$ if and only if $\exists c, N>0$ such that $\forall x > N, f(x) < cg(x)$.
Big-O notation explicitly ignores constant factors (this is what the $c$ does in the definition), so any statement in big-O notation about $f(x)=x$ will also hold for $f(x)=2x,f(x)=1000x,$ and $f(x)=\frac{1}{2^{100}}x$.
What big-O notation tells you is that, asymptotically, one function is bounded by another. So if $f(x)=x$ and $g(x)=x^2$ then $f=O(g)$. This remains true when we replace $g$ with $g'(x)=x^2-2^{100}$ or with $g''(x)=210x^2-10$. The $N$ in the definition is what establishes this is an asymptotic property. The notation doesn't tell you anything about how good the bound is though. $f=O(f)$ is always true, as is $f=O(2^f)$. Concretely, if $f(x)=x$ then $f=O(g)$ for any polynomial $g$, as well as pretty much anything that looks like $2^x$.
There is a parallel notation for lower bounds (the "big-Omega" notation), which is $f=\Omega(g)$ which has precisely the same definition but the inequality is reversed. When $f=\Omega(g)$ AND $f=O(g)$ then we say that $f=\Theta(g)$ (the "big-theta" notation). There is also little-omega and little-theta with the same basic idea, but they are similar to the little-o notation.
These symbols can also be defined explicitly in terms of limits, as seen here. However that way of thinking about the notation is more limited and is not always defined.