# Splitting summations?

From CLRS Introduction to Algorithms, Appendix A, page 1152. They discuss a method called "Splitting Summations", where they split the summation and bound each term separately. For example,

\begin{align*} \sum_{k=1}^{n} k &= \sum_{k=1}^{n/2} k + \sum_{k=n/2 + 1}^{n} k\\ &\geq \sum_{k=1}^{n/2} 0 + \sum_{k=n/2 + 1}^{n} (n/2)\\ &= (n/2)^2\\ &= \Omega(n^2)\,\end{align*}

I get step 1, that makes sense, but I didn't understand step 2 where they have replaced $$k$$ with $$0$$ in one part and $$k$$ with $$n/2$$ in the other. Why did they do this?

Thanks!

## 1 Answer

In the first sum, you know that k ≥ 0. In the second sum, you know k ≥ n/2. Therefore, adding k in the first sum is ≥ adding 0 in the first sum, and adding k in the second sum is ≥ adding n/2 in the second sum.

You can adapt this for example to show that the sum of $$k^5$$ for 1 ≤ k ≤ n is $$O(n^6)$$: You have n/2 terms each at least $$n^5/32$$, for a total of $$n^6/64 = O(n^6)$$. Or a lower bound for n!, where you have a product including n/2 terms each larger than n/2, so n! > $$(n/2)^{n/2}$$.

• Its the ≥ that messed me up. Thank you for explaining that! – cds333 Nov 1 '19 at 22:34