1
$\begingroup$

I have recently encountered a series of perturbation problems in which the Big Oh notation is used frequently. Since I have not encountered this notation before, I am a little bit confused about it. I have read various websites about it, and I get the idea behind it (I also can quite easily look at a function and determine what order the function has), but a few statements in my text book still leave me confused.

For instance, in my book it says the following at one point:

Consider

$q(x,\epsilon) = y_{0} + y_{1} = e^{1-x} + e(1 - e^{-x/ \epsilon})$

If $x = O(1)$, then

$q(x, \epsilon) = e^{1-x} + e + O(\epsilon)$

I am a little bit confused about the whole "If $x = O(1)$, then. . ." part of the problem. Why is it here necessary to state this? Is this because, if $x = O(1)$, then we have $x < A$, where $A$ is a constant? Thus $x$ does not approach infinity, and then the last estimation above follows? Is this correct reasoning? This is what I assume based on how I've interprerted the definition of Big Oh, but I could be wrong here.

I would greatly appreciate it if someone could explain this to me.

|cite|improve this question
$\endgroup$
  • $\begingroup$ The $x = O(1)$ seems a bit strange indeed. If $x \to \infty$ the result still holds, while it goes wrong for $x \to 0$, e.g. $x = \epsilon$. So I think they should have written something like $x = \Omega(1)$, i.e. $x$ is constant or increasing as $\epsilon \to 0$. $\endgroup$ – TMM Mar 5 '12 at 13:21
  • $\begingroup$ Where are you reading that assertion? Is $\epsilon$ and $x$ assumed to be both positive? Because if $x = O(1)$ but $x < 0$, the estimate that $e\cdot e^{-x/\epsilon}$ by $O(\epsilon)$ as $\epsilon \to 0$ is false. Furthermore, if $x = O(\epsilon)$ as $\epsilon \to 0$, you also have $x = O(1)$. But then $x/\epsilon = O(1)$ and so $e\cdot e^{-x/\epsilon}$ is again not $O(\epsilon)$. Maybe given more context it would be clear what the author(s) intended, but as written the quoted parts doesn't look right to me (and so you have every reason to be confused). $\endgroup$ – Willie Wong Mar 5 '12 at 13:21
  • $\begingroup$ @Willie: Like I said, the author probably meant "If $x = \Omega(1)$". And yeah, sure, $\epsilon$ could be negative as well... (which contradicts the use of $O(\epsilon)$ in the next formula) $\endgroup$ – TMM Mar 5 '12 at 13:45
  • $\begingroup$ Thanks a lot for your comments! Yes, I see now that it is obvious that it does not really matter if x goes to infinity as the result will still hold. Unfortunately I do not have the text book in front of me now since I am at work. It will therefore be a couple of hours until I can provide the full context. This is from section 6.7 in Jordan and Smith's "Nonlinear ordinary differential equations", so if anyone of you have this book, you may find the whole problem there. I really appreciate your input though! Thanks a lot! $\endgroup$ – Kristian Mar 5 '12 at 13:49
2
$\begingroup$

I think there is confusion because usually when we talk about Big-Oh, it is assumed that $n\rightarrow\infty$. However, when we are talking about 'small quantities' like $\epsilon$, then we mean that $\epsilon\rightarrow0$ instead. You can think of it as $\epsilon=\frac{1}{n}\rightarrow 0$.

You can see the term $e^{1-x/\epsilon}$ is smaller than $\epsilon$. So we say it is $O(\epsilon)$. A graph on wolframalpha may convince you by ploting $e^{1-1/x}-x$ on x=0..1. See here

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you for the answer. Yes, I see that the term is smaller than $\epsilon$. However, I still do not quite get why we are stating that $x$ has to be $O(1)$- $\endgroup$ – Kristian Mar 5 '12 at 14:17
  • 2
    $\begingroup$ I took a look at your book. It is finding an approximation on $0\le x\le1$. So by O(1), I guess he means x is independent of epsilon...Then in the next line, he showed when $x=\zeta \epsilon$. $\endgroup$ – FiniteA Mar 5 '12 at 14:40
  • $\begingroup$ OK. Thanks a lot. It makes sense that the notation may be used to indicate independence from epsilon! $\endgroup$ – Kristian Mar 5 '12 at 15:21

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.