Find $\sum_{i=0}^{\log n} \frac{1}{2^i}$

333 Views Asked by At

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}$

1

There are 1 best solutions below

1
On

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)$.