Big Theta Proof: May I chose any constant?

Question

I have the following assignment:

Prove that $\sum^n_{i=1} i2^i \in \Theta(n2^n)$

My current approach thus far is the following:

Since we need to prove $k_1 \cdot n2^n \le \sum^n_{i=1} i2^i \le k_2 n2^n$ I chose $k_1 = 1$ and $k_2 = 2$. This holds true to my condition. However I'm unsure whether I can just freely decide on using those two.

Therefore my question is:

Am I allowed to chose any constant factor I want in a $\Theta$ proof (given that the condition holds true)?

Answer 1

Yes, as long as the constant conforms to the definition of $\Theta$, that is it

• is positive and
• independent of $n$.

This follows directly from the definition of $\Theta$, which requires only the existence of some $c_1, c_2>0$ (in typical formulations).

You may find our reference questions helpful; in particular, there are more convenient ways to prove such claims besides checking the definition explicitly.