2
$\begingroup$

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)?

$\endgroup$
  • 4
    $\begingroup$ Any positive constant ;-) $\endgroup$ – Tom van der Zanden May 6 '15 at 12:45
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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