1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Simply Beautiful Art Aug 20 '17 at 11:45
  • $\begingroup$ 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$. $\endgroup$ – Masacroso Aug 20 '17 at 11:48
1
$\begingroup$

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.

$\endgroup$

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.