# Proving $\Omega(cf) = \Omega(f)$

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?

• 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. Commented Oct 2, 2012 at 17:48
• yes you are right, it is obvious but it was a bit hard for me to prove it formally. Commented Oct 2, 2012 at 19:58
• 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.) Commented Oct 2, 2012 at 20:00
• 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. Commented Oct 3, 2012 at 14:34
• Fair enough. But don't you have TAs, or fellow students who understood the material better than you? Commented Oct 3, 2012 at 15:27

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

• 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*}

• This does not tell the OP where specifically the problems in their proposed proof are. Commented Oct 3, 2012 at 11:57
• 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 :). Commented Oct 3, 2012 at 14:16
• @Raphael Hmm yes, you have a good point. I might fill that in later this evening if I have the time. Commented Oct 3, 2012 at 14:22

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.

• hmm yes you are right. I'll update the post and I'm going to add my second proof. Commented Oct 2, 2012 at 19:52

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)\}$.

• 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)$." Commented Jun 15, 2016 at 11:00
• 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$
– Leo
Commented Jun 15, 2016 at 12:09
• 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$. Commented Jun 15, 2016 at 12:11