0
$\begingroup$

I think I understand the definition of the big-Oh notation as well that of the small-Oh notation. But I wonder about the limits.

I understand that

$ f = o(g):\quad\lim_{x \rightarrow a} \,\left|\frac{f}{g}\right| = 0 $

because f becomes insignificant in relation to g as x aproaches infinity. I do not understand

$f = O(g):\quad\limsup_{x \rightarrow a}\, \left|\frac{f}{g}\right| < \infty$

though...

I get that it only makes sense to look at the upper limit as $\frac{f}{g}$ might osculate. As I see it the biggest $\frac{f}{g}$ can get if it was not for c is 1 because of $f \leq c*g$ in the definition of big-Oh

So does this mean that for a big c we can get arbitrarily close to infinity? This is the part where I can't see clearly.

Any help?

$\endgroup$
3
  • $\begingroup$ No. $c$ has the role of $\limsup_{x \to a} |f/g|$, which is finite. $\endgroup$
    – Crostul
    Nov 5, 2016 at 13:32
  • $\begingroup$ @Crostul I think that helped. So the c from $f \leq c*g$ determins the upper limit for $\lim\limits_{n \to \infty}\frac{f(n)}{g(n)}$. And thus the upper limit has to be of constant value below infinity? $\endgroup$
    – omnesia
    Nov 5, 2016 at 13:50
  • $\begingroup$ @Crostul okay now I got it.... c actually is the limit facepalm. Thank you very much $\endgroup$
    – omnesia
    Nov 5, 2016 at 13:57

1 Answer 1

Reset to default
0
$\begingroup$

As pointed out to me by @Crostul

$f(n) \in O(g(n)):\ \limsup\limits_{n \to \infty}|\frac{f(n)}{g(n)}| < \infty$

is correct because

$O(g(n))\ =\ \{f(n):\ \ \exists c,\ n_0\ \forall n \geq n_0\ :\ 0\ \leq\ f(n)\ \leq\ c*g(n)\}$

with a fixed and finite c. This means:

$\limsup\limits_{n \to \infty}|\frac{f(n)}{c*g(n)}| = 0$

and thus

$\limsup\limits_{n \to \infty}|\frac{f(n)}{g(n)}| = c < \infty$

At least I hope this is correct.

$\endgroup$
2
  • $\begingroup$ It's not correct, unfortunately. Assuming all functions positive to avoid writing the absolute value, from the inequality $f(n) \leqslant c\cdot g(n)$ for $n \geqslant n_0$, we obtain $\frac{f(n)}{g(n)} \leqslant c$ for all $n \geqslant n_0$, and therefore $$\limsup \frac{f(n)}{g(n)} \leqslant c.$$ Taking the greatest lower bound of the set of constants such that we have $f(n) \leqslant b\cdot g(n)$ for large enough $n$, we find $$\limsup \frac{f(n)}{g(n)} = \inf \{ b > 0 : (\exists n_0)(n \geqslant n_0 \implies f(n) \leqslant b\cdot g(n))\}.$$ $\endgroup$
    – Daniel Fischer
    Nov 5, 2016 at 14:28
  • $\begingroup$ Thank you very much @DanielFischer. I would have loved it if my Professor had explained it like this $\endgroup$
    – omnesia
    Nov 5, 2016 at 14:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .