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
    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
    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
    Ok sorry, my bad.2012-02-20