4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The last three statements of your answer are false. An $O$/$\Omega$/$\Theta$ relationship does not tell you that the limits exist. What if $f(x) = 1$ and $g(x) = 1 + \sin(x)/2$? Then $f = \Theta(g)$ but neither $\lim f/g$ nor $\lim g/f$ exist. $\endgroup$ – Antonio Vargas Jan 3 '17 at 0:09
  • $\begingroup$ @AntonioVargas interesting point! I appear to have been to hastey, though I think it's true when the limits exist? Intuitively, it should be related to the sup/inf of the set of values of $c$ that satisfy the definition. $\endgroup$ – Stella Biderman Jan 3 '17 at 0:10
  • $\begingroup$ The last three statements are definitely false. $\endgroup$ – user66307 Mar 14 '17 at 20:11
  • $\begingroup$ @Lembik Huh, I thought I had fixed this a while ago. They are now correct. $\endgroup$ – Stella Biderman Mar 14 '17 at 20:28
  • $\begingroup$ The limit $\lim{x \to \infty} f(x)/g(x)$ does not have to exist . $\endgroup$ – user66307 Mar 14 '17 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.