3
$\begingroup$

If we have the function $f : \mathbb{N}_0 \rightarrow \mathbb{N}$ with $f(n) = n^2$ and we look at the following representations of the sets $\mathcal{o}(f),\mathcal{O}(f),\Theta(f),\Omega(f),\omega(f) $: Asymptotic Notation

Now I have to list all necessary statements which are proving that the illustration is correct.

The necessary statements are in my opinion:

\begin{align} \Theta (f)&\subseteq \mathcal{O}(f) \\ \Theta (f)&\subseteq \Omega (f) \\ \Theta (f)&= \mathcal{O}(f) \cap \Omega (f) \\ \omega (f)&\subseteq \Omega (f) \\ \hbox{o}(f)&\subseteq\mathcal{O}(f) \\ \, \emptyset &=\, \omega (f) \cap \hbox{o}(f) \end{align} Now I have to proof two statements of my choice. But how to proof that in a formal correct way. (I understand the intuitive proofs but I don't know how to do it formally correctly.)

Hope somebody can help.

$\endgroup$
  • $\begingroup$ 1) You have some redundant statements. 2) You are missing proper subset relations. 3) You are missing statements about $o$/$\omega$ and $\Theta$. 4) Proving these statements is just using the definitions. See also here. $\endgroup$ – Raphael Nov 7 '16 at 15:54
1
$\begingroup$

Here is an explanation by example. Let $\Theta'(f) = \{ g : g(n)/f(n) \text{ tends to a positive limit} \}$. I will show that $\Theta'(f) \subseteq \Theta(f)$. The first step is to write the definitions. There are several variants of the definitions, and I picked one arbitrarily; you should use the definitions that were stated in class.

Let $f\colon \mathbb{N} \to \mathbb{N}$.

  1. $\Theta'(f)$ consists of all functions $g\colon \mathbb{N} \to \mathbb{N}$ such that for some positive $x \in \mathbb{R}_+$, $\lim_{n\to\infty} g(n)/f(n) = x$.
  2. $\Theta(f)$ consists of all functions $g\colon \mathbb{N} \to \mathbb{N}$ such that for some positive $a,b \in \mathbb{R}_+$ and $n_0 \in \mathbb{N}$, for all $n \geq n_0$ it holds that $a f(n) \leq g(n) \leq b f(n)$.

The next step is to take a function $g \in \Theta'(f)$.

Let $g \in \Theta'(f)$. Then there exists a positive $x \in \mathbb{R}_+$ such that $$ \lim_{n\to\infty} \frac{g(n)}{f(n)} = x.$$

Finally, we have to show that $g \in \Theta(f)$. For that we have to come up with positive $a,b \in \mathbb{R}_+$ and $n_0 \in \mathbb{N}$ such that $af(n) \leq g(n) \leq bf(n)$ for all $n \geq n_0$.

By the definition of limit, there exists $n_0$ such that for $n \geq n_0$, $$ \left|\frac{g(n)}{f(n)}-x\right| \leq \frac{x}{2}. $$ Therefore for $n \geq n_0$, $$ \frac{x}{2} \leq \frac{g(n)}{f(n)} \leq \frac{3x}{2}, $$ implying $$ \frac{x}{2} f(n) \leq g(n) \leq \frac{3x}{2} f(n). $$ Taking $a = x/2$ and $b = 3x/2$, we see that $g \in \Theta(f)$.

Only the latter two steps really belong to the proof. The first one states the claim. It is a very important step — without knowing what you're trying to prove, you won't be able to prove it.

$\endgroup$

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.