2
$\begingroup$

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!

$\endgroup$

2 Answers 2

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Its the ≥ that messed me up. Thank you for explaining that! $\endgroup$
    – cds333
    Commented Nov 1, 2019 at 22:34
0
$\begingroup$

Here you want to obtain a lower bound (big-omega) for your sum expression. The idea is to carefully split the summation into two parts so that it leads to your desired result, which is $\Omega(n)$ in this case. Here, they have split the sum into two halves. For the first half, they have replaced all entries with 0, which is smaller than all of them. Similarly, for the second half, they have replaced all with $n/2$, which is smaller than all integers between $n/2+1$ and $n$. Thus, the first sum vanishes while the second sum simplifies to $(n/2)^2$, and we get the required result.

Now to answer the 'why' of your question: Simply because it works! One can, in fact, use any constant $c > 1$ and get the same result.

$\sum\limits_{k=1}^{n} k = \sum\limits_{k=1}^{n-\lceil n/c\rceil} k + \sum\limits_{n-\lfloor n/c\rfloor + 1}^{n} k \ge \sum\limits_{k=1}^{n-\lceil n/c\rceil} 0 + \sum\limits_{n-\lceil n/c\rceil + 1}^{n} \lceil n/c\rceil = (\lceil n/c\rceil)^2 \ge (n/c)^2 = \Omega(n^2)$

$\endgroup$

Your Answer

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

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