Order of growth from summation $$\sum_{i=0}^n (i)$$
$$\sum_{i=0}^n (i^2 + 2^i)$$
$$\sum_{i=0}^n (i^2+n)$$
I am trying to find the order of growth of these summations.Right hand side of the summations are confusing me. Do they matter at all when we try to find their asymptotically growth rate? Are all of these summations are Theta(n)?
 A: We use big-Oh notation in order to describe the growth of the sums when $n$ tends to infinity. Each of the finite sums admits a closed formula representation. From this representation we can identify the dominant term with respect to growth.

We obtain
  \begin{align*}
\color{blue}{\sum_{i=0}^ni}&=\frac{n(n+1)}{2}=\frac{1}{2}n^2+\frac{n}{2}\\
&\color{blue}{=O(n^2)}
\end{align*}
\begin{align*}
\color{blue}{\sum_{i=0}^n (i^2 + 2^i)}&=\sum_{i=0}^ni^2+\sum_{i=0}^n2^i\\
&=\frac{n(n+1)(2n+1)}{6}+\frac{1-2^{n+1}}{1-2}\tag{1}\\
&=\left(\frac{1}{3}n^3+\frac{1}{2}n^2+\frac{1}{6}n\right)+\left(2^{n+1}-1\right)\\
&\color{blue}{=O(2^n)}\tag{2}
\end{align*}
\begin{align*}
\color{blue}{\sum_{i=0}^n (i^2 + n)}&=\sum_{i=0}^ni^2+n\sum_{i=0}^n1\\
&=\left(\frac{1}{3}n^3+\frac{1}{2}n^2+\frac{1}{6}n\right)+n(n+1)\\
&\color{blue}{=O(n^3)}
\end{align*}

Comment:


*

*In (1) we use the finite geometric sum formula.

*In (2) we observe that $2^{n+1}=2\cdot2^n=O(2^n)$ or equivalently $O(2^{n+1})=O(2^n)$.

*The results indicate $\sum_{i=0}^ni^k=O(n^{k+1})$.
A: Hint:
for growth you need to look only on the part in the sum that growth the fastest, so you can ignore half of the second and the third expressions 
