2

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?

Searene
  • 981
  • 3
    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}$. – Valborg Sep 26 '16 at 00:49

1 Answers1

1

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.

Simply Beautiful Art
  • 74,685
  • 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$ – reuns Sep 26 '16 at 01:13