I'm trying to work through a pretty basic regular expansion problem in my textbook but I'm getting tripped up by the use of Big O notation.

I understand the formal definition of Big O notation, but here it seems to be being used to denote terms on the order of what the argument of the Big O is, and I don't really understand how this is related to the formal definition. Most of the examples I can find of Big O problems talk about "finding" the Big O notation for some function by proving something like, for example, $f(x) = \mathcal{O}(x^{4})$, using the formal definition. This seems to me to imply that a function has only one Big O notation.

However, in this example in the book, as well as most examples I remember encountering in the past, they're taking several different Big O's of the equation by comparing the $\mathcal{O}(1)$, or $\mathcal{O}(\epsilon)$, or $\mathcal{O}(\epsilon^{2})$ terms on either side of the equation to make sure they cancel out so that the expansion can be solved. At first this seemed to make sense to me. It seemed like the $\mathcal{O}(1)$ terms were all the ones without any factors of $\epsilon$, the $\mathcal{O}(\epsilon)$ terms were all the ones with a factor of $\epsilon$, the $\mathcal{O}(\epsilon^{2})$ terms were all the ones with a factor of $\epsilon^{2}$, and so on and so on. But once they got to $\mathcal{O}(\epsilon^{2})$ they started getting results I wouldn't expect if my assumptions were correct, so I went back to the formal definition to try to figure out what was going on, and now I'm even more confused.

Can someone give me, or at least point me to, some explanation of how Big O notation is applied in this context, and possibly even how the formal definition makes this kind of application possible.

EDIT: Although I'm still not 100% solid on this application of Big O notation, I've just confirmed that my primary source of confusion in the instance was caused by a typo in the textbook.

  • $\begingroup$ It is $\epsilon$ a constant? Another question, to context,from what book this comes? $\endgroup$ – Masacroso Mar 1 '17 at 8:02
  • $\begingroup$ What textbook are you using? A little context here could mean a lot. Can you provide an excerpt from the book? $\endgroup$ – Akay Mar 1 '17 at 8:04
  • 1
    $\begingroup$ @Masacroso In this case $\epsilon$ is a small positive number and for the overall problem we're trying to solve $x^{2} + 2\epsilon x - 1 = 0$ for $x$ using a regular expansion. The book is Introduction to the Foundations of Applied Mathematics by Holmes (2009). $\endgroup$ – bones_mccoy Mar 1 '17 at 8:06
  • $\begingroup$ The big O notation means that exists some $M>0$ and $x_0$ such that $$|f(x)|\le M 1|g(x)|\iff f(x)\in\mathcal O(g(x),\quad\forall x\ge x_0$$ This imply that for any two constants $a,b \in\Bbb R$ if $f(x)\in\mathcal O(a)$ then $f(x)\in\mathcal O(b)$. Then in your examples $\mathcal O(1)=\mathcal O(\epsilon)=\mathcal O(\epsilon^2)$, if $\epsilon$ is a constant. $\endgroup$ – Masacroso Mar 1 '17 at 8:10
  • $\begingroup$ It is most probable that $\epsilon\to0$. In this case, every quantity $f(\epsilon)$ in $O(\epsilon^2)$ is also in $O(\epsilon)$ (but not the opposite) and every quantity $f(\epsilon)$ in $O(\epsilon)$ is also in $O(1)$ (but not the opposite). To sum up, one has strict inequalities between $O$-classes, such as $$O(\epsilon^2)\subset O(\epsilon)\subset O(1)$$ A consequence is that, if $f(\epsilon)=O(\epsilon^a)$ then $f(\epsilon)=O(\epsilon^b)$ for every $b<a$. $\endgroup$ – Did Mar 1 '17 at 8:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.