0

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?

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

1 Answers1

0

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.

omnesia
  • 101
  • 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))}.$$ – Daniel Fischer Nov 05 '16 at 14:28
  • Thank you very much @DanielFischer. I would have loved it if my Professor had explained it like this – omnesia Nov 05 '16 at 14:57