2
$\begingroup$

According to Wikipedia, big O notation characterizes functoins according to their growth rates, but I have some confusion about it. For example, we say

$f(x)=O(g(x))$ as $x\rightarrow a$

if and only if there exist positive numbers $\delta$ and $M$ such that

$|f(x)|\leq M|g(x)|$ for $|x-a|< \delta$

Here I set

$f(x)=x+1, g(x)=100, a = 0, \delta = 1, M = 1$

So I can say $x+1=O(100)$ as $x\rightarrow 0$

because there exist positive numbers $\delta = 1$ and $M=1$ such that

$|x+1|\le |100|$ for $|x| < 1$

This comes the part that confuses me, because according to some interpretations on wikipedia, big o notation denotes the grow rate of functions, so if $x+1=O(100)$, the growth rate of $f(x)=x+1$ should less or equal than $g(x) = 100$. But the growth rate of $g(x)=100$ is zero because it doesn't grow on y axis at all! So of course $f(x)=x+1$ grows faster than $g(x)=100$, which contradicts the result of the big no notation, why?

$\endgroup$
  • 3
    $\begingroup$ The point that is confusing you is that you are using two distinct invocations of Big-Oh: one that is going towards infinity, and one that is going to a finite point. Be very careful that you do not mix the two, or as you have experienced firsthand, confusion follows. Notice that the very first definition on that page has $x \rightarrow \infty$, and only later do they mention $x \rightarrow a$. We would most likely only use the finite point version if our function had a pole of some kind, like the function $\frac{1}{x^2}$. $\endgroup$ – Valborg Sep 26 '16 at 0:49
1
$\begingroup$

You have the first line correct:

According to Wikipedia, big O notation characterizes functoins according to their growth rates

But you forget to define what growth rates measure. In essence, growth rate is how fast a function reaches $\pm\infty$, for example:

$$\lim_{x\to0}e^{-1/x^2}$$

$$\lim_{x\to5}\frac x{x-5}$$

Both limits "grow" to infinity. The concept of growth rate here only applies to things that approach infinite magnitudes.

The second scenario is that we are considering functions as $x$ approaches $\pm\infty$. For example:

$$\lim_{x\to\infty}\frac x{x-5}$$

$$\lim_{x\to-\infty}e^x$$

The third scenario is that it is used to explain the behavior of a function around a point. For example:

$$e^x=1+x+\mathcal O(x^2)$$

Once you have that down, everything else is fine.

$\endgroup$
  • $\begingroup$ it is unclear, we use $g(x) = \mathcal{O}(f(x)), = o(f(x)), \sim f(x)$ not only as $x \to \infty$, and not only when $|g(x)| \to \infty$ $\endgroup$ – reuns Sep 26 '16 at 1:13

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.