Why is $\sum_{j=1}^n (n-j+1) \ge \sum_{j=\lceil n/2 \rceil}^n (n/2) \ge n^2/4$?

32 Views Asked by At

This is the snippet of which the amount of calls should be determined as tightly and simplified as possible.

for j = 1,...,n do
    for k = j,...,n do
        f()

This is the equation to determine the amount of calls (lower bound) of a function in a nested loop (dependant on n): $$\sum_{j=1}^n \sum_{k=j}^n 1 = \sum_{j=1}^n (n-j+1) \ge \sum_{j=\lceil n/2 \rceil}^n (n/2) \ge n^2/4$$

While I understand the equality of the first two summations, I can't quite grasp why $\sum_{j=1}^n (n-j+1) \ge \sum_{j=\lceil n/2 \rceil}^n (n/2)$.
I have especially a hard time with understanding why $\sum_{j=\lceil n/2 \rceil}^n (n/2) \ge n^2/4$.

Completeness wise, it would follow from this that $n^2 \in O(\sum_{j=1}^n \sum_{k=j}^n 1)$. However, this part is clear to me and doesn't need further explanation.

1

There are 1 best solutions below

0
On BEST ANSWER

\begin{align} \sum_{j=1}^n \sum_{k=j}^n 1 &= \sum_{j=1}^n (n-j+1)&&\text{put $i=n-j+1$}\\ &= \sum_{i=1}^n i\\ &\geq \sum_{i=\lceil n/2 \rceil}^n i&&\text{by $1\leq\lceil n/2 \rceil\leq n$}\\ &\ge \sum_{i=\lceil n/2 \rceil}^n (n/2)\\ &=(n-\lceil n/2 \rceil+1)(n/2)\\ &\ge n^2/4&&\text{by $\lceil n/2 \rceil<n/2+1$} \end{align}