Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
6  
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 1

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.