How to find upper and lower bound without using formula?

Question

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

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.

Answer 1

1) Notice that $P(n) = \sum_{i=1}^{n} i = \frac{n(n-1)}{2} \leq n^{2} \implies P(n) \in O(n^{2})$.

Or perhaps you would prefer: $P(n) = \sum_{i=1}^{n} i \leq \sum_{i=1}^{n} n = n^{2}$. This gives you $P(n) \in O(n^{2})$.

Then you can show $n^{2} \leq 3P(n)$ to get $P(n) \in \Omega(n^{2})$.

2) Use the same trick. $P(n) = \sum_{i=0}^{n} (n + i) \leq \sum_{i=0}^{n} 2n = 2 \sum_{i=0}^{n} n = 2n^{2}$. Then just apply the techniques from part (1).

Answer 2

For 1) if $n = 2k$, then $P(n) = P(2k) = 1+2+3+\cdots + 2k = (1+2k) +(2+ (2k-1)) + (3+(2k-2)) + \cdots + (k+(2k-(k-1))) = (2k+1) +(2k+1) + \cdots + (2k+1) = k(2k+1) = \dfrac{n}{2}\cdot (n+1) = \dfrac{n(n+1)}{2}$.

If $n = 2k+1$, then:

$1 + 2 + 3 +\cdots + (2k+1) = (1+2+3+\cdots + 2k) + (2k+1) = (1+2+\cdots + +(n-1)) + n = \dfrac{(n-1)n}{2} + n = \dfrac{n(n+1)}{2}$.

For 2) $n + (n+1) + (n+2) +\cdots + 2n = (n+n+n+\cdots + n) + (1+2+3+\cdots + n) = n\cdot n + \dfrac{n(n+1)}{2} = n^2 + \dfrac{n(n+1)}{2}$

Answer 3

For $P(n) = 1 + 2 + 3 + \cdots + n,$ there are $n$ terms on the right and none is greater than $n,$ so $P(n) \leq n^2$ and therefore $P(n) = O(n^2).$ On the other hand, the last $\left\lceil \dfrac n2 \right\rceil$ terms are each at least $\dfrac n2$, so $P(n) \geq \left\lceil \dfrac n2 \right\rceil \left(\dfrac n2\right) \geq \dfrac{n^2}{4},$ and $P(n) = \Omega(n^2).$

Alternatively, observe that the first $\left\lfloor \dfrac n2 \right\rfloor$ terms can be paired with the last $\left\lfloor \dfrac n2 \right\rfloor$ like this: $1 + n,$ $2 + (n-1),$ $3 + (n-2),$ etc., so $P(n) \geq \left\lfloor \dfrac n2 \right\rfloor n.$ But this is very close to finding that $P(n) = \dfrac{n(n+1)}{2},$ which you're not supposed to do, so maybe that's not such a clever idea for this exam.

The reasoning for the other series is similar except that you don't have to do the trick with ignoring the first half of the series.