Using the definition of Big-Theta to prove a theorem.

370 Views Asked by At

If $f(n) \in \Theta(n)$ and $g(n) \in \Theta(n)$, then $f(n) + g(n) \in \Theta(n)$

I'm supposed to prove the following theorem below using the definition of $\Theta(n)$. I know the definition of Big-Theta, but I don't understand how to use it prove the theorem. I'd prefer to NOT be given a full proof to this theorem as I'd like to learn how to do this myself. But if possible, any guidance on how to start this would be great!

1

There are 1 best solutions below

2
On

Start with the definition: There are constants $a_1$ and $a_2,$ $b_1$ and $b_2,$ such that $$ a_1n < f(n) < a_2n $$ $$ b_1n < g(n) < b_2n $$ for sufficiently large $n$.

Now you want to say something about $f(n) +g(n).$ Can you use the above inequalities to to get an inequality for $f(n)+g(n)$? See if you can put it into the form where it fits the definition of $\Theta(n)$ for some new constants $c_1$ and $c_2$ that you can derived from previously defined quantities.