1

I'm not too familiar with formal analysis so I'm probably thinking about this all-wrong. I have looked at several posts on SE on big-O notation. The closest to my query seemed to be this one, but it didn't quite get at my difficulty...

I was looking at the definition for Big-O notation. When Big-O notation was skimmed over in lectures, the definition was given as "$f(x)=O(g(x))$ as $x\to a$ iff there exists a $c\geq 0$ and $\delta \geq 0$ s.t. $|f(x)|\leq c|g(x)|$ for all $|x-a|<\delta$" (I now know it would be more correct to say $f(x)\in O(g(x))$)

Firstly, it seems that Wikipedia excludes the point $x=a$ from this, which I am finding confusing. Wolfram Alpha doesn't give a definition like this, and in some lecture notes from MIT OCW here the definition includes the point $x=a$, as in my lectures. Hoping someone could clarify this.

My main difficulty, however, is reconciling this formal definition with the more wordy definition of "$f(x)\in O(g(x))$ means $f$ has a rate of growth that is smaller than or equal to that of $g$".

I was trying to figure out how these two definitions are equivalent, but was having some trouble with it. Going from the first to the second definition, I have say

$\frac{f(x)-f(a)}{x-a} \leq \frac{cg(x)-f(a)}{x-a}$ taking both functions as positive for now.

but then I don't think there is anything more I can say. I was trying to show that the derivative (rate of growth) of $f$ must be less than that of $g$ but the problem is that, even though $f(a)\leq c(g(a))$ is the definition form my lectures holds (where x=a is included), I cannot say that $cg(x)-cg(a)\geq f(x)-f(a)$. And even a sketch shows that this need not be the case:

(gradient of f is clearly greater than that of g about x=a)

So then I thought that perhaps the definition with regards to the rate of change applied only to the case of $a=\infty$, but again I have trouble proving this because f could be wiggling around below g all the way up to infinity, so it is difficult to talk about gradients.

Perhaps I am thinking about this wrong and Big-O notation refers to approach on a global rather than local scale? So in places it can indeed be the case that the rate of growth of f exceeds that of g, but not overall or else f would eventually overtake g?

Masacroso
  • 30,417
Meep
  • 3,167
  • I think you are confusing what is meant by "rate of growth". Particularly, it is looking at the rate at which $f(x)\to f(a)$ compared to the rate at which $g(x)\to g(a)$, where $f$ and $g$ are continuous. For example, $x$ approaches $0$ slower than $x^2$. – Simply Beautiful Art Aug 20 '17 at 11:45
  • big-Oh at a point $a$ of a function $f$ means that $|f|$ is bounded by $M |g|$ (for some $M>0$ and some function $g$) in a neighborhood of $a$. Then we says that $f\in\mathcal O(g), x\to a$. – Masacroso Aug 20 '17 at 11:48

1 Answers1

1

Why would we exclude the point $a$? We may want to say $$ \frac{1}{\sin t} = O\left(\frac{1}{t}\right)\qquad\text{as } t \to 0 $$ even though both functions are undefined at $t=0$.

As in that example: When using the "rate of growth" language, we are probably thinking that both $f$ and $g$ go to $\infty$. So we are asking whether one of them goes to $\infty$ faster than the other.

GEdgar
  • 111,679