3
$\begingroup$

I was reading on the big O/little O notation etc. and I understand the definitions, but how exactly would I use it to find the order of an expression/function?

I am asked to determine the order of $\sqrt{\epsilon(1-\epsilon)}$ and $4\pi^2\epsilon$ as $\epsilon \rightarrow 0$. But how would I do that?

  • 0
    You should divide by the $\epsilon^p$ and see for which $p$ the expression goes to zero as $\epsilon$ goes to zero. Then choose an $\epsilon$ near the supremo of such p's.2012-02-20
  • 0
    Thanks @chessmath. May I ask -- where does the $\epsilon ^p$ come from?2012-02-20
  • 0
    The main idea is that $\epsilon^p$ is an infinitesimal of order $p$ and an infinitesimal of "larger" order goes to zero "fast".2012-02-20

3 Answers 3

1

For $\sqrt{\epsilon(1-\epsilon)}$, note that $(1-\epsilon)$ isn't small at all as $\epsilon \to 0$, so all that matters is the $\epsilon$.

For $4\pi^2\epsilon$, the $4 \pi^2$ is just a constant, so it does not affect the order of the zeroness.

-1

Big-Oh means that, simply speaking, asymptotically, $ \forall \epsilon < \epsilon' \ \exists \ C>0$ s.t. the ratio of the functions $f,g$ are upper-bounded by $C$. In such case we write $f=O(g)$. In your case:

$$ \lim_{\epsilon \to 0}\frac{\sqrt{\epsilon(1-\epsilon)}}{4 \pi^2 \epsilon} = \frac{1}{4 \pi^2} \lim_{\epsilon \to 0}\sqrt{\frac{\epsilon(1-\epsilon)}{\epsilon^2}} = \infty $$
this means that there are no such $ \epsilon', \ C$ that $ \forall \epsilon <\epsilon' \ f(\epsilon) \leq C g(\epsilon)$. Since the limit of the ratio is $\infty$, we write $f=\omega(g)$ or equivalently $g=o(f)$.

  • 0
    Thanks. Sorry, perhaps I should make the question clearer --- I am trying to find the order of $\sqrt{\epsilon(1-\epsilon)}$ and the order of $4\pi^2\epsilon$. Its 2 separate questions.2012-02-20
  • 0
    the order of the first function is $o(\sqrt{\epsilon})$, the second one $o(\epsilon)$ as $\epsilon \to 0$2012-02-20
  • 0
    Thanks. May I ask, how did you get/what is your method to get $o(\sqrt{\epsilon})$ for $\sqrt{\epsilon(1-\epsilon)}$?2012-02-20
  • 0
    for $\epsilon \to 0 \ \sqrt{\epsilon - \epsilon^2}$ is dominated by the first term (since squaring a value between 0 and 1 gives a lower value), therefore the largest term in this expression is $\sqrt{\epsilon}$ and the order of convergence is $o(\sqrt{\epsilon})$2012-02-20
-1

You may do as in the following way:

$$\frac{(\epsilon(1-\epsilon))^{1/2}}{\epsilon^p}=\epsilon^{{0.5}-p}(1-\epsilon)^{0.5}$$

Which goes to zero when $\epsilon$ goes to zero iff $p<0.5$ in this case is $o(\epsilon)$. When $p=0.5$ we have $O(\epsilon)$. The other case is analogous.

  • 0
    I'm not sure what you mean. $\sqrt{\epsilon (1-\epsilon)}$ is $\Theta(\epsilon^{0.5})$, but $w(\epsilon) = \epsilon^{0.5-p} (1-\epsilon)^{0.5}$ isn't $o(\epsilon)$ for $p<0.5$, because it would mean that $w(\epsilon)/ \epsilon$ is bounded for small $\epsilon$, which is not true. I would rather say that it is $o(1)$.2012-02-20
  • 0
    Hi savicko, could you explain to me how you got $o(1)$ as your answer?2012-02-20
  • 0
    No, my answer for $\sqrt{\epsilon (1-\epsilon)}$ is $\Theta(\epsilon^{0.5})$ as I stated above. But $w(\epsilon)$ is $o(1)$ if $p<0.5$.2012-02-20
  • 0
    Ok sorry, my bad.2012-02-20