# If $f(n) = \Theta(g(n))$, then $cf(n) = \Theta(g(n))$ for any $c \neq 0$

How would I prove:

If $f(n) = \Theta(g(n))$, then $cf(n) = \Theta (g(n))$ for any $c \neq 0$.

I'm pretty sure it's true, but not sure how to prove it.

-
What is your definition of $\Theta$ notation? The ones I know can be applied directly to make the proof almost immediate. –  Henning Makholm Oct 26 '11 at 2:34

## 1 Answer

Suppose that $f(n)$ is $\Theta(g(n))$ and that $c\ne 0$. You need to show that $cf(n)$ is both $O(g(n))$ and $\Omega(g(n))$; let’s look at $O$.

You know that $f(n)$ is $O(g(n))$, so write out what this means: there is some $n_0$ and some constant $M>0$ such that $$|f(n)|\le M|g(n)|\tag{1}\text{ whenever }n\ge n_0.$$ You want some $m_1$ and $M_1>0$ such that $|cf(n)|\le M_1|g(n)|$ whenever $n\ge n_1$. Now $|cf(n)|$ = $|c||f(n)|$, so this amounts to saying that you want $n_1$ and $M_1>0$ such that $$|c||f(n)| \le M_1|g(n)|\tag{2}\text{ whenever }n\ge n_1.$$ Can you see how to choose $n_1$ and $M_1$ in terms of $n_0$ and $M$ so that $(1)$ implies $(2)$?

Once you’ve done that, you can apply exactly the same kind of reasoning to $\Omega$.

-