2
$\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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ In the second line, notice that it starts with $\ge$. $\endgroup$
    – Rick Decker
    Dec 23, 2015 at 17:36
  • $\begingroup$ what book is CLRS? $\endgroup$
    – miracle173
    Dec 23, 2015 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, 2015 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, 2015 at 23:29
  • $\begingroup$ @miracle173, I very much doubt that. $\endgroup$
    – vonbrand
    Dec 30, 2015 at 19:43

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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