1
$\begingroup$

I'm studying discrete math for tomorrow's exam and got stuck in the below question. I tried to google it and couldn't find anything useful.

Prove the following sum is $\Theta (n^2)$ (we have to find $O(n^2)$ and $\Omega (n^2)$)

  1. $P(n)= 1+2+3+4\cdots + n$

  2. $P(n) = n+(n+1)+(n+2)+\cdots +2n$

Note you cannot use any formula you have to do it my algebraic manipulation. This might be simple but I am not getting any clue right now and I dont have solution of it.

$\endgroup$
  • $\begingroup$ Wikipedia shows you how to derive that the first sum is $\tfrac12n(n+1)$ and the second sum is the first sum plus $n^2$. $\endgroup$ – David Richerby Dec 15 '14 at 8:18
5
$\begingroup$

Another approach:

  • $n^2/4=(n/2)^2= \underbrace{n/2 + n/2 +\cdots + n/2}_{n/2 \text{ times}} \le 1+2+\cdots + n \le \underbrace{n + n +\cdots + n}_{n \text{ times}} = n^2 $

  • $n^2= \underbrace{n + n +\cdots + n}_{n \text{ times}} \le n+(n+1)+\cdots + 2n \le \underbrace{2n + 2n +\cdots + 2n}_{n \text{ times}} = 2n^2 $

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Hint: For the first case of $P(n)$

  1. Rewrite in reveresed order the right side of $P(n)$ to make another expression for $P(n)$.
  2. Sum these expressions for $P(n)$
  3. Solve the equation for $P(n)$. You should get it something like this. $$ 2 P(n) = n (n+1) \leq (n+1)^2 \in O(n^2) $$

$$ 2 P(n) = n (n+1) \geq n^2 \in \Omega(n^2) $$

Then, $P(n)\in \Theta(n^2)$.

For the second case, you could do the same thing that in the previous one, it just difference by $n$ so factorize it.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ you can add that this is gauss trick and may give some historical importance. $\endgroup$ – Phani Raj Feb 10 '15 at 13:14
0
$\begingroup$

Clue: You only need to prove it, instead of finding it out. Mathematical induction is for this. IMO, this is what the problem wants you to do.

| cite | improve this answer | |
$\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.