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$
  • $\begingroup$ No. $c$ has the role of $\limsup_{x \to a} |f/g|$, which is finite. $\endgroup$ – Crostul Nov 5 '16 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 '16 at 13:50
  • $\begingroup$ @Crostul okay now I got it.... c actually is the limit facepalm. Thank you very much $\endgroup$ – omnesia Nov 5 '16 at 13:57
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$
  • $\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 '16 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 '16 at 14:57

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.