Asymptotic analysis: difference between big O and big Omega limits?

Question

So I've started university again after taking a break and my first assignment in algorithms is to prove whether $f(n)$ is in Big O / Big Omega of $g(n)$. These are the limit rules I have:

$$\lim\limits_{n\to\infty} \frac{f(n)}{g(n)} < \infty \Longrightarrow f \in O(g) \\ \lim\limits_{n\to\infty} \frac{f(n)}{g(n)} = 0 \Longrightarrow f \in o(g) \\ \lim\limits_{n\to\infty} \frac{f(n)}{g(n)} > 0 \Longrightarrow f \in \Omega(g) \\ \lim\limits_{n\to\infty} \frac{f(n)}{g(n)} = \infty \Longrightarrow f \in ω(g)$$

My question is: What is the difference between Big O and Big Omega in terms of limits? Isn't every value bigger than $0$ also smaller than infinity?

Also the following problem: $$\lim\limits_{n\to\infty} \frac{n+\pi}{n-e^{2021}} \text{ with l'Hopital} = \frac{1}{1} = 1$$ So it would be $>0$, so Big Omega, but if I do l'Hopital again, it comes down to zero, meaning small $o$...? Am I missing something here? My brain is still hazy from the long break, so maybe I'm confusing simple things here ;)

Answer 1

The Big Omega notation

The definition of the Big Omega $\Omega$ notation may cause confusion. Quoting Wikipedia:

Unfortunately, there are two widespread and incompatible definitions of the statement $$f(x)=\Omega(g(x))\quad (x\rightarrow a),$$ where $a$ is some real number, $∞$, or $−∞$, where $f$ and $g$ are real functions defined in a neighbourhood of $a$, and where $g$ is positive in this neighbourhood. The first one (chronologically) is used in analytic number theory, and the other one in computational complexity theory. When the two subjects meet, this situation is bound to generate confusion.

The Hardy–Littlewood definition

In 1914 Godfrey Harold Hardy and John Edensor Littlewood introduced the new symbol $\Omega$, which is defined as follows

$$f(x)=\Omega(g(x))\ (x\rightarrow\infty)\;\iff\;\limsup_{x \to \infty} \left|\frac{f(x)}{g(x)}\right|> 0$$

The Knuth definition

In 1976 Donald Knuth published a paper to justify his use of the $\Omega$-symbol to describe a stronger property. Knuth wrote: "For all the applications I have seen so far in computer science, a stronger requirement ... is much more appropriate". He defined $f(x)=\Omega(g(x))\Leftrightarrow g(x)=O(f(x))$, in other words $$f(x)=\Omega(g(x))\ (x\rightarrow\infty)\;\iff\;\liminf_{x \to \infty} \left|\frac{f(x)}{g(x)}\right|> 0.$$

Difference between the Big O notation and the Big Omega notation

Since you stated that this exercise is an assignment in algorithms we will use the Knuth definition of $\Omega$. Let's look at the definitions again:

$$f=O(g) \iff \limsup_{x \to \infty} \left|\frac{f(x)}{g(x)}\right| < \infty, \qquad f=\Omega(g)\;\iff\;\liminf_{x \to \infty} \left|\frac{f(x)}{g(x)}\right|> 0$$

We have three major differences here.

1. Big $O$ is defined as a limit superior, whereas Big $\Omega$ is defined as a limit inferior.

2. The limit in the Big $O$ definition can be equal to zero, whereas the limit in the $\Omega$ definition has to be strictly greater than zero.

3. The limit in the $\Omega$ notation is allowed to go to $+\infty$.

So if $f= O(g)$, $|f|$ is asymptotically bounded above by $g$ and if $f=\Omega(g)$, $\lvert f\rvert$ is asymptotically bounded below by $g$.

If we look at the definition with quantifiers, we can also see how these definitions differ, $$ \begin{align} f&=O(g) \iff \exists\ c > 0\ \exists\ x_0 > 0\ \forall\ x > x_0: |f(x)| \le c\cdot|g(x)|,\\ \qquad f&=\Omega(g) \iff \exists\ c > 0\ \exists\ x_0 > 0\ \forall\ x > x_0: c\cdot \lvert g(x)\rvert\le|f(x)|. \end{align} $$

The limit and l'hopital

Let's look at the limit first. By l'hopital the solution is indeed $1$,

$$\lim\limits_{n\to\infty} \frac{n+\pi}{n-e^{2021}}= \lim\limits_{n\to\infty} \frac{\frac{\mathrm{d}}{\mathrm{d}n}(n+\pi)}{\frac{\mathrm{d}}{\mathrm{d}n}(n-e^{2021})} = \frac{1}{1} = 1.$$

One important condition which has to be satisfied if applying l'hopitals rule on $\lim_{x\to c}f(x)/g(x)$ is that $\lim_{x\to c}f'(x)/g'(x)$ must exist. From this it follows that you cannot apply l'hopital on $1/1$, since $\frac{\mathrm{d}}{\mathrm{d}n}(1)/\frac{\mathrm{d}}{\mathrm{d}n}(1)=0/0$ does not exist.

Now we can safely state that

$$n+\pi=\Omega(n-e^{2021})$$

and that

$$n+\pi \neq o(n-e^{2021}).$$

Here $\neq$ is being used loosely. Remark: By definition, if a function is in $\Omega$ it cannot be in $o$.

We may also say that $n+\pi = O(n-e^{2021})$ and the sharper statement $n+\pi \sim n-e^{2021}$, which is equivalent to the limit you evaluated earlier.

Answer 2

1. For first: using for big-$\mathrm{O}$ $\boldsymbol{\lim \sup}$ gives more clear and right understanding, only limit can not work here, as you correctly doubt.

Let me add, also, that ratio form is not most general form for asymptotic definitions. For example, when we use in definitions of type $\frac{f}{g}$, then we lost cases for such $g$, which can have zero values. So, if we take definition without limits, then it's clear from scratch, that big-$\mathrm{O}$ gives boundedness for $f$ from above, by a constant multiple of $g$, while big-$\Omega$ gives boundedness for $f$ from below, by a constant multiple of $g$.

2. For second question: you can use l'Hopital* in certain conditions, $\frac{0}{0}$ or $\frac{\infty}{\infty}$, but at last step you have not this.

Application of l'Hopital sometimes meet more subtle mistakes, because conditions of theorem rarely checked. Most times people use l'Hopital without thinking about theorem's conditions: when see $\frac{0}{0}$ or $\frac{\infty}{\infty}$ they immediately shoot from l'Hopital rifle, which can be dangerous. For example, should exists limit for $\frac{f'}{g'}$. If you take $\frac{x^2 \sin \frac{1}{x}}{\sin x}$, when $x \to 0$, then it is not possible to use l'Hopital by mentioned reason. Also l'Hopital required $f'^2+g'^2\ne 0$, or $g' \ne 0$, in limit point some neighbourhood. If we take $\frac{x-\sin x }{x+\sin x }$ when $x \to \infty$, then again is not possible to use l'Hopital.

$\ast ~$ L'Hopital is also spelled l'Hospital (from old french) or l'Hôpital (modern french).

Answer 3

Let's restate l’Hôpital's Rule

Let $a,b$ be two real numbers such that $a<b$. Let $\ell$ be a real number or $\pm \infty$.

Let $\displaystyle f$ and ${\displaystyle g}$ two differentiable functions ${\displaystyle \left]a,b\right[}$ such that ${\displaystyle g'\neq 0}$

1. if $\displaystyle \lim_a f(x)=\lim_a g(x)=0$ & $\displaystyle\lim_{a^+}\frac{f'(x)}{g'(x)}=\ell $ then $\displaystyle\lim_{a^+}\frac{f(x)}{g(x)}=\ell $

2. If $\displaystyle \lim_a f(x)=\lim_a g(x)=+\infty$ & $\displaystyle\lim_{a^+}\frac{f'(x)}{g'(x)}=\ell $ then $\displaystyle\lim_{a^+}\frac{f(x)}{g(x)}=\ell $

The problem is you can only apply l'Hôpital if you get an indeterminate form which is not the case of $\frac11$

Your result is therefore correct it is big $\Omega$.

Note that when the fraction is equal to one we often say that $f$ is equivalent to $g$ noted $f \sim g$

Here you don't even need to use l'Hôpital to conclude : just factor both the numerator and denominator by $n$.

Now when it comes to the notation :

A picky note first, all these letter are greek including the big-Oh ($\text{Omicron}$) therefore, one should note $\text{O}$ and not $O$ but thats neatpicking

Note that most often we consider positive-valued function, therefore you may ignore the $|\cdot|$ in what follows.

What $f=\text{O}(g)$ means is that $|f|$ is bounded above by some constant multiple of $|g|$ that is from a certain value $N$ on, we can find a positive constant $c$ such that $$|f(n)| \leq |g(n)|\cdot c$$

or for quantifier boys out there $$f=\text{O}(g)\iff \exists c\in\mathbb{R}_+^*, \exists N \in \mathbb{N} \; \forall n \in \mathbb{N},n>N\implies|f(n)| \leq |g(n)|\cdot c$$

$\Omega$ means the reverse condition holds* , that is $$f=\Omega(g)\iff \exists c\in\mathbb{R}_+^*, \exists N \in \mathbb{N} \; \forall n \in \mathbb{N},n>N\implies|g(n)|\cdot c \leq |f(n)|$$

We can in fact say: $$f=\text{O}(g) \iff g=\Omega(f)$$

* not exactly the logic negation but that's the idea