1
$\begingroup$

I'm trying to prove the following lemma:

$c$ is a positive real number and $f, g$ are functions from natural numbers to non-negative real numbers. I'm trying to prove rigorously that:

$\Omega(cf(n))$ = $\Omega(f(n))$.

I know that it is obvious but I'm trying to construct a proof that is as complete as possible. My current approach is like this:

This lemma is equivalent to saying that: $f(n) \in \Omega(cf(n))$ iff $cf(n) \in \Omega(f(n))$.

We can also restate that as:

  1. If $t(n) \in \Omega(cf(n))$ then $t(n) \in \Omega(f(n))$.
  2. If $t(n) \in \Omega(f(n))$ then $t(n) \in \Omega(cf(n))$.

For 1.,

$(*)$ $\exists d_1, d_2 \gt 0, \forall n \gt n_0, n_1, \forall n \in N$:

$t(n) \ge d_1cf(n)$ and $t(n) \ge d_2f(n)$

Now let's fix $d_1, d_2$ and $n_0, n_1$ to be any constants that fulfils $(*)$, such that: $n'=max\{n_0, n_1\}$ and $d_1c \ge d_2$, using this we can say that:

$t(n) \ge d_1cf(n) \ge d_2f(n)$ and hence the 1. is satisfied because $t(n) \in \Omega(cf(n)), \Omega(f(n))$. The proof of 2. is mutatis mutandis.

Do I have a mistake in my proof, is there a better/more elegant way to prove this lemma? Shortly how can I improve this?

$\endgroup$
  • 2
    $\begingroup$ Please note that check-my-proof questions are typically boring for others if the the answer is a simple "yes" (or "no)", especially if the task is as simple as unfolding the definition twice. $\endgroup$ – Raphael Oct 2 '12 at 17:48
  • $\begingroup$ yes you are right, it is obvious but it was a bit hard for me to prove it formally. $\endgroup$ – systemsfault Oct 2 '12 at 19:58
  • 1
    $\begingroup$ My above statement is independent of the level of the question. (Nevertheless, in my experience questions of basic level -- meaning the asker is likely to have problems with the basics -- yield better results when discussed at a blackboard with a teacher.) $\endgroup$ – Raphael Oct 2 '12 at 20:00
  • $\begingroup$ In fact that this was a question from an assignment of a course I took last semester and I got zero point with the proof I wrote above. In the beginning I was planning to write the proof in the assignment that phantom pointed out. But I found it too simple and instead wrote the one in the post. Now I was trying to figure out my mistake and find the correct solution as an exercise. The problem about the professor is that he is very busy person and it is very hard to find him outside his classes. $\endgroup$ – systemsfault Oct 3 '12 at 14:34
  • $\begingroup$ Fair enough. But don't you have TAs, or fellow students who understood the material better than you? $\endgroup$ – Raphael Oct 3 '12 at 15:27
2
$\begingroup$

I think you're trying to take too many steps at once. Try to think about it one small step at a time.

Always think about:

  • What are the definitions I have available
  • What do I know already? What is proven?

Proving sets equal

Since you have two sets, $\Omega(cf)$ and $\Omega(f)$ and you want to prove them equal, you first need to think about what it means for two sets to be equal:

$$A = B \Longleftrightarrow A \subseteq B \land A \supseteq B$$

This tells you, that you need to show two things:

  1. $\Omega(cf) \subseteq \Omega(f)$
  2. $\Omega(cf) \supseteq \Omega(f)$

Proving $A$ to be a subset of $B$

For this, you need to apply the definition of $A \subseteq B$:

$$ A \subseteq B \Longleftrightarrow \forall a \in A:(a \in B)$$

Nature of our proof

As you can probably see by now, our proof will have the following form:

$$\begin{align*}"\subseteq":\\ & \text{Let } g \in \Omega(cf):\\ &\Rightarrow \dots\\ &\Rightarrow g \in \Omega(f) \end{align*} $$

The proof goes the same way for $"\supseteq"$.

Filling in the dots

Keeping this structure in mind, the path you need to follow is already laid out.

Using this definition for \Omega: $ \Omega(f) = \{ g |\, \exists\, n_0 \in \mathbb{N}, c > 0 \forall n \geq n_0: cf(n) \leq g(n) \} $

One direction of the proof could look as follows:

$$\begin{align*}"\subseteq":\\ & \text{Let } g \in \Omega(cf): \\ &\Rightarrow \exists\, n_0\in \mathbb{N}, c'>0: c'cf(n) \leq g(n)\ \ \forall n \geq n_0 &\text{definition of } \Omega\\ &\Rightarrow \exists\, d>0, n_0\in \mathbb{N}: d f(n) \leq g(n)\ \ \forall n \geq n_0 &\text{Let } d=c'c\\ &\Rightarrow g \in \Omega(f) &\text{definition of } \Omega \end{align*} $$

$\endgroup$
  • $\begingroup$ This does not tell the OP where specifically the problems in their proposed proof are. $\endgroup$ – Raphael Oct 3 '12 at 11:57
  • $\begingroup$ yeah thanks the explanation, the filling in the dots part was actually the second proof that I had in my mind :). At least you've approved my second proof, before I wrote it :). $\endgroup$ – systemsfault Oct 3 '12 at 14:16
  • $\begingroup$ @Raphael Hmm yes, you have a good point. I might fill that in later this evening if I have the time. $\endgroup$ – phant0m Oct 3 '12 at 14:22
1
$\begingroup$

Why do such $d_1, d_2$ always exist?

You might not be able to increase $d_1$ indefinitely in order to fulfil $d_1c\geq d_2$ because $t(n) \geq d_1cf(n)$ might break along the way.

$\endgroup$
  • $\begingroup$ hmm yes you are right. I'll update the post and I'm going to add my second proof. $\endgroup$ – systemsfault Oct 2 '12 at 19:52
-1
$\begingroup$

My opinion is that the $=$ sign should be interpreted as $\subset$ in the asymptotic complexity context. Consider the case when we write $n^2=\Omega(n)$. This is mentioned in CLRS's "Introduction to Algorithms", page 49.

Another point is that considering the definition of $\Omega$, it naturally hides constant coefficients inside, so you can show the "equality" easily by stating $c_2=c\cdot c_1$, defined as follows:

$\Omega(f)=\{g|∃n_0∈N,c_2>0∀n≥n0:c_2f(n)≤g(n)\}$, $\Omega(cf)=\{g|∃n_0∈N,c_1>0∀n≥n0:c_1\cdot cf(n)≤g(n)\}$.

$\endgroup$
  • $\begingroup$ No, the equals sign should be interpreted as equality. The question is equivalent to "Prove that $g\in\Omega(cf)$ if, and only if, $g\in\Omega(f)$." $\endgroup$ – David Richerby Jun 15 '16 at 11:00
  • $\begingroup$ ok...why not...it depends on what does the OP want. I sometimes see things like $\Omega(n^2)=\Omega(n)$ in which $=$ means $\subset$ $\endgroup$ – Leo Jun 15 '16 at 12:09
  • $\begingroup$ Well, in this case, the two sets are equal, so it certainly shouldn't mean $\subset$. And being asked to prove that $A\subseteq B$ is a very different thing to being asked if $A\subset B$ or $A\subseteq B$. $\endgroup$ – David Richerby Jun 15 '16 at 12:11

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.