1
$\begingroup$

I'm reading Cormen, Leiserson, Rivest and Stein, 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 didn't understand step 2 where they have replaced $k$ with $0$ in one part and $k$ with $n/2$ in other. How does this method work? Can anybody explain?

$\endgroup$
  • 1
    $\begingroup$ In the second line, notice that it starts with $\ge$. $\endgroup$ – Rick Decker Dec 23 '15 at 17:36
  • $\begingroup$ what book is CLRS? $\endgroup$ – miracle173 Dec 23 '15 at 22:57
  • 1
    $\begingroup$ @miracle173 Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, MIT Press. This is actually a pretty standard abbreviation in the computer science community: if you Google for "CLRS", all the top hits refer to the right thing. (I'm not criticizing you for not Googling; just presenting evidence why using the abbreviation isn't crazy.) $\endgroup$ – David Richerby Dec 23 '15 at 23:11
  • $\begingroup$ @DavidRicherby: You are right but maybe the result is a different if you google in five years or if you use duckduckgo or if you live in Kazakhstan $\endgroup$ – miracle173 Dec 23 '15 at 23:29
  • $\begingroup$ @miracle173, I very much doubt that. $\endgroup$ – vonbrand Dec 30 '15 at 19:43
2
$\begingroup$

$$\begin{align*} 55 = 1 + 2 + \dots + 10 &= (1 + 2 + 3 + 4 + 5) + (6 + 7 + 8 + 9 + 10)\\ &\color{red}{\geq} (0 + 0 + 0 + 0 + 0) + (5 + 5 + 5 + 5 + 5) \\ &= (10/2)(10/2) = 25\,.\end{align*}$$

If you're wondering how to come up with such substitutions, there's no general method: this is one of the creative things you have to do to produce mathematical proofs.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.