Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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