I need some help understanding how to prove that n log n in the equation below is the dominating term. i.e. Given the equation below, find function f(n) such that T(n) = $\theta$(f(n)):
$T(n) = \sum_{i=1}^{n} \frac{n\;log\;n . i^2}{2^i}$
Intuitively, I would argue that n log n is the dominating term (and hence $\theta(n\;log\;n)$). However I don't understand how I can prove this.
I realize that $\frac{i^2}{2^i}$ is a geometric series. If I can prove that it converges to a constant C, then I can show that n log n dominates. However I don't quite understand how I can go about doing this. Any tips?
$$\sum_{i=0}^\infty x^i=\frac1{1-x}$$ Differentiate that with respect to $x$: $$\sum_{i=0}^\infty ix^{i-1}=\sum_{j=0}^\infty(j+1)x^j=\frac1{(1-x)^2}$$ Rearrange it a little, and you can find $\sum i/2^i$. Differentiate again, rearrange it again, and you can find $\sum i^2/2^i$. This is a finite number, as you guessed. $$T(n)=n\log n\sum_{i=0}^{\infty}\frac{i^2}{2^i}=n\log n\sum_{i=0}^{\infty} i^2(\frac12)^i$$