0

Definition of $\mathcal O, o, \mathcal {\Omega}, \omega , \mathcal \Theta$ interms of limit

can any 1 please tell me is following correct?

$f(n)=\mathcal {O}(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = c > 0 $, c is a constant

$f(n)=\mathcal {o}(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0 $

$f(n)=\mathcal {\Omega}(g(n)) \iff \lim_{n \to \infty} \frac{g(n)}{f(n)} = c > 0 $, c is a constant

$f(n)=\mathcal {\omega}(g(n)) \iff \lim_{n \to \infty} \frac{g(n)}{f(n)} = 0 $

can you enlighten me definition of $\Theta$ in terms of limit definition. Also please correct me if i am going wrong in above

Also in Using Limits to Determine Big-O, Big-Omega, and Big-Theta and http://web.mit.edu/broder/Public/asymptotics-cheatsheet.pdf it is given that $lim_{n \to \infty} f/g \neq 0, \infty \iff f=\Theta(g)$ (How??)

Also please elaborate on how they got

$lim_{n \to \infty} f/g \neq \infty \iff f=\mathcal O(g)$ (How??)

$lim_{n \to \infty} f/g \neq 0 \iff f=\Omega(g)$ (How??)

Nascimento de Cos
  • 793

1 Answers1

1

So, it's more correct to think about these asymptotic notations as sets. While it is okay to say $f(n) = O(g(n))$, it is more correct to say that $f(n) \in O(g(n))$.

A correction: $$f(n) \in O(g(n)) \Longleftrightarrow \lim_{n\rightarrow \infty} \frac{f(n)}{g(n)} = c$$

A similar correction can be made for your definition for $\Omega(g(n))$. It follows that $O(f(n)) \subset o(f(n))$ and that $\Omega(f(n)) \subset \omega(o(f(n))$.

And your other definitions can be equivalently rewritten. $\Theta(f(n))$ is the intersection of $O(f(n))$ and $\Omega(f(n))$. So: $$f(n) \in \Theta(g(n)) \Longleftrightarrow f(n) \in O(g(n)) \wedge f(n) \in \Omega(g(n)) \Longleftrightarrow \lim_{n\rightarrow \infty}\frac{f(n)}{g(n)}$$

Jacob Dunleavy
  • 11
  • can you please elaborate on last statement? if $f \in O(g)$ and $f \in \Omega(g)$ implies as $n \to \infty$, $f/g \to c, g/f \to c'$ (c,c' are some constants greater than zero, as per my definition if correct in above). – Nascimento de Cos Oct 17 '19 at 18:32