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