# Is this why this summation is equivalent to this Theta notation?

So I'm not sure if I misunderstood the lesson or not. $$T(n) =\sum_{j=2}^{n}\Theta(j) = \Theta(n^2)$$ Are these equivalent because: $$\sum_{j=2}^{n}\Theta(j) = \frac{n(n-1)}2 - \frac{1(1 - 1)}{2} = \frac{n(n-1)}2$$ $$\frac{n^2-n}2$$ and these are equal because in theta we only get the highest order term and drop the constant? $$\frac{n^2-n}2 = \frac12n^2 - \frac12 n = \Theta(n^2)$$ Did I misunderstand something or did I get the lesson correctly? thanks!

-

Your understanding is correct, subject to one minor error and what some would call a lack of rigor. Let's get the minor error out of the way first. Ignoring the theta for the moment, we should have $$\sum_{j=2}^n j = \left(\sum_{j=1}^n j\right)-1=\frac{n(n+1)}{2}-1=\frac{n^2+n-2}{2}$$ rather than $n(n-1)/2$.
That's minor, as I said, and will have no effect on the ultimate outcome. Now let's address the rigor. You are correct in this instance by treating $\Theta(j)$ as substantially like $j$. What it actually means is that for any function $f(m)\in\Theta(j)$ we'll have three positive constants $c, d$, and $M$ such that $$c\; j\le f(m)\le d\; j\text{, for all }m\ge M$$ In other words, any such $f$ will eventually be bounded above and below by constants.
Your sum, $\sum_{j=2}^n\Theta(j)$, will then involve several functions which we may call $f_j(m)$, each of which comes with three constants which we'll denote by $c_j, d_j$, and $M_j$ such that $$c_j\; j\le f_j(m)\le d_j\; j\text{, for all }m\ge M_j$$ so we'll actually have $\sum_{j=2}^n\Theta(j)=\sum_{j=2}^n f_j(m)$. By the above constraints, then, we'll have $$\sum_{j=2}^n c_j j\le\sum_{j=2}^n f_j\le\sum_{j=2}^n d_j j$$ Now let $\hat{c}=\min_{2\le j\le n}\{c_j\}$ and $\hat{d}=\max_{2\le j\le n}\{d_j\}$. Then we'll have $$\hat{c}\sum_{j=2}^n j\le\sum_{j=2}^n c_j j\quad\text{ and }\quad\sum_{j=2}^n d_j j\le\hat{d}\sum_{j=2}^n j$$ so $$\hat{c}\frac{n^2+n-2}{2}\le\hat{c}\sum_{j=2}^n j\le\sum_{j=2}^n f_j\le \hat{d}\sum_{j=2}^n j\le\hat{d}\frac{n^2+n-2}{2}$$ which, by the definition of $\Theta$, means that $$\sum_{j=2}^n f_j=\sum_{j=2}^n\Theta(j)=\Theta\left(\frac{n^2+n-2}{2}\right)=\Theta(n^2)$$ as you correctly intuited.