Does the big o notation always denotes the grow rate of the function?

178 Views Asked by At

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?

1

There are 1 best solutions below

1
On BEST ANSWER

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.