1
$\begingroup$

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!

1 Answers 1

2

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.