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

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?

• The symbol $k$ is bound variable on both sides and can be replaced with any other symbol unequal with $n$ and $f$ without changing the meaning of sum. Apr 11 at 8:11
• math.stackexchange.com/questions/4252549/… Apr 11 at 16:36
• @zkutch Thank you very much, I have read the explanation in the linked question and answer. What I understand is that on the left we have $n$ asymptotic bounds on $n$ $f\left ( k \right )$ instances, while on the right-hand side, we effectively have one function $g\left ( n \right )=\sum_{k=1}^{n} f\left ( k \right )$ of $n$ variable an have one asymptotic bound thereon Apr 11 at 19:07
• I agree with the vision that, possibly, on the left side we have a finite sum of sets created by asymptotic notation for a finite family of functions, but for greater formal clarity, I wrote an answer. Apr 12 at 1:31

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

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)$$

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)$$.
1. 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)$$
2. 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).