Linearity property of summation applied to Big Theta notation (CLRS math background appendix)

Question

Section A.1 of the Mathematical Appendix of the CLRS, the third edition, page 1146, contains the following formula stating linearity property of summation applied to $\Theta$ notation: $$ \sum_{k=1}^{n}\Theta\left ( f \left ( k \right ) \right )=\Theta \left ( \sum_{k=1}^{n} f\left ( k \right )\right ). $$ And states that the $\Theta$-notation on the left-hand side applies to the variable $k$, but on the right-hand side, it applies to $n$. How does $\Theta$-notation come to apply to a variable, if it applies to functions? What is implied here?

Answer 1

The expression $\Theta(f(k))$ stands for a function $g(k)$ which is $\Theta(f(k))$, that is, there exist $C>c>0$ and $K>0$ such that $cf(k) \leq g(k) \leq Cf(k)$ for all $k \ge K$. In this sense, $\Theta(f(k))$ is with respect to $k$, since it only has to apply for large $k$.

Here is what the equation in CLRS says, verbosely:

Suppose that $g(k) = \Theta(f(k))$. Then $$ \sum_{k=1}^n g(k) = \Theta\left(\sum_{k=1}^n f(k)\right). $$

Even more verbosely:

Let $f,g$ be functions mapping positive integers to positive reals.

Suppose that there exist constants $C>c>0$ and $K>0$ such that $cf(k) \leq g(k) \leq Cf(k)$ for all $k \ge K$. Then there exist constants $D>d>0$ and $N>0$ such that $$ d\sum_{k=1}^n f(k) \leq \sum_{k=1}^n g(k) \leq D\sum_{k=1}^n f(k).$$ for all $n \ge N$.

For the proof, we pick $N = K$. Let $S_g = \sum_{k=1}^K g(k)$ and $S_f = \sum_{k=1}^K f(k)$. If $n \geq N$ then $$ \sum_{k=1}^n g(k) \geq \frac{S_g}{S_f} \sum_{k=1}^K f(k) + c \sum_{k=K+1}^n f(k) \geq \min\left(\frac{S_g}{S_f},c\right) \sum_{k=1}^n f(k). $$ Similarly, $$ \sum_{k=1}^n g(k) \leq \frac{S_g}{S_f} \sum_{k=1}^K f(k) + C \sum_{k=K+1}^n f(k) \leq \max\left(\frac{S_g}{S_f},C\right) \sum_{k=1}^n f(k). $$ Therefore we can take $d = \min(S_g/S_f,c)$ and $D = \max(S_g/S_f,C)$.

In fact, similar reasoning shows that for positive functions, the definition of big Theta remains the same even if we remove $K$ from the picture, requiring the inequalities to hold for all inputs. However, the proof above can be extended to functions satisfying weaker conditions. For example, it suffices that $\liminf_{k\to\infty} f(k) > 0$. In this case, we have $f(k) \geq \eta$ for some $\eta > 0$ and all $k \geq L$, and so $$ \sum_{k=1}^{M_f} f(k) \geq \sum_{k=1}^L f(k) + (M_f-L)\eta, $$ which is positive for some $M_f \geq L$. Similarly, $$ \sum_{k=1}^{M_g} g(k) \geq \sum_{k=1}^{\max(K,L)} g(k) + (M_g-\max(K,L))c\eta, $$ which is positive for some $M_g \geq \max(K,L)$. Taking $M = \max(M_f,M_g)$, we can repeat the above proof, replacing $K$ with $M$.

Answer 2

In mathematics we have so-called variable-binding operators, such as, for example, composite sum and product, with respect to finite family of some monoid's elements. In same way we can consider $\Theta$ notation.

In our case we have two such operators in one and same expression. If we have symbol $k$ as bound variable of sum, then we need also some symbol for bound variable for Theta, which represent variable for function inside Theta. This brings us to the one of the possible refinements $$\sum_{k=1}^{n} \Theta\big(f_k(x)\big) = \Theta\left(\sum_{k=1}^{n} f_k(x)\right),x \to x_0\quad(1)$$ Now in left hand we have algebraic finite sum of sets $\Theta\big(f_k(x)\big),x \to x_0$ (each is same with $\Theta\big(f_k\big)$), which equal to set defined on right hand. Following expression, possibly, wouldn't raise so many questions $$\sum_{k=1}^{n} \Theta\big(f_k\big) = \Theta\left(\sum_{k=1}^{n} f_k\right)\quad(2)$$

Addition.

The wonderful answer from Yuval Filmus gives me possibility to express the following thoughts, in the hope, that they will be useful

1. Mathematics is an attempt to unambiguously express one's thought in writing and convey it to another person, even if a conversation is impossible. This led to the creation of many formal rules that some people find complicated and cumbersome, but make the concept of a question more understandable to others.

The given example is a case, when a formally formulated statement makes it just ambiguous for specialists.

The mentioned book itself defines - page 44 - asymptotic notations as sets. The expression $\Theta\big(g(n)\big)$ is uniquely defined by the function $g$ and hides the dummy variables $c_1, c_2, n_0$ and $n$, were with respect to last variable is considered asymptotic. If the function $g$ depends on a single variable, then it makes no sense to write $\Theta\big(g(n)\big)$ and the notation turns into $\Theta\big(g\big)$. To be pedantic, if/when we insist on definition based on set, we cannot use dummy variable inside $\Theta$ for operators like sum from outside, because formally $\Theta\big(g(n)\big) = \Theta\big(g(k)\big) = \Theta\big(g\big)$. On the other hand, for example, $\Theta\big(f(1)\big)$, $\Theta\big(f(2)\big)$ etc., expresses a completely different meaning than, perhaps, the authors wanted to put into this statement. Formally $\Theta\big(f(1)\big) = \Theta\big(1\big)$.

2. Problem of page 1146 is not in understanding right-hand side as applied to $n$, but, as is written in book, in sentence "$\Theta$-notation on the left-hand side applies to the variable $k$". Based on what was written in the previous point, we cannot formally understand the left-hand side exactly. Probably, better to sacrifice brevity for the sake of a clear understanding of the issue and, following the adjacent answer, write $$\text{if } g \in \Theta(f)\text{, then }\sum\limits_{k=1}^{n} g(k) \in \Theta\left(\sum\limits_{k=1}^n f(k)\right)\quad(3)$$

3. On page 1146 formula under discussion is considered as "linearity property ". But to express the well-known property of linearity in mathematics for $\Theta$, then we do not need even $n$ summands, but is enough two ones: $\Theta$ is linear means $\Theta(f+g)=\Theta(f)+\Theta(g)$, but not $(3)$. If we insist on $n$ summands, then we can write it as (2).