0
$\begingroup$

I'm not really sure how to solve summations, so any help would be great. In particular, I had thought that $n^2\sum_{i=0}^{\log n} \frac{1}{2^i}=O(n^2\log n)$ but it's actually $O(n^2)$, and I'm trying to make sure that I don't make that mistake again. Are there any resources that can help me solve other common summations using pen-and-paper?

Other summations (I don't have to solve these, but they're typical of what I would encounter):

$\sum_{i=1}^{ n} i$

$\sum_{i=1}^{\log n} 3^i$

$\sum_{i=0}^{n} 1.01^{-1}$

$\endgroup$
  • $\begingroup$ Note that $\sum_{i\ge 0}\frac1{2^i}=2$, so $n^2\le n^2\sum_{i=0}^{\log n}\frac1{2^i}\le 2n^2$, giving you $O(n^2)$ without actually computing the finite sum. $\endgroup$ – Brian M. Scott Oct 23 '14 at 1:46
0
$\begingroup$

Well, if $f(n)=O(n^2)$ then $f(n)=O(n^2\log n)$ by definition, so you aren't wrong, there is just a better bound.

The trick is knowing that $\sum_{i=0}^\infty \frac{1}{2^i}=2$. So $\sum_{i=0}^{\log n} \frac{1}{2^j} = O(1)$.

$\endgroup$
  • $\begingroup$ Sorry, that's what I meant. I was trying to find the tightest bound. $\endgroup$ – Ashley Oct 23 '14 at 1:49

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.