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$
1

1 Answer 1

5
$\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$
12
  • 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$ Jan 3, 2017 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$ Jan 3, 2017 at 0:10
  • $\begingroup$ The last three statements are definitely false. $\endgroup$
    – user66307
    Mar 14, 2017 at 20:11
  • $\begingroup$ @Lembik Huh, I thought I had fixed this a while ago. They are now correct. $\endgroup$ Mar 14, 2017 at 20:28
  • $\begingroup$ The limit $\lim{x \to \infty} f(x)/g(x)$ does not have to exist . $\endgroup$
    – user66307
    Mar 14, 2017 at 20:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .