Splitting summations?

Question

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!

Answer 1

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