Sums and Products of Big Theta Notation (CLRS)

Question

I'm working through the 4th edition of CLRS, and I'm having difficulties understanding what the following pair of starred problems ask (p. 73):

★ f. Prove that for $S \subseteq \mathbb{Z}$, we have

$$\sum_{k \in S} \Theta\left( f(k) \right) = \Theta \left( \sum_{k \in S} f(k) \right), $$

assuming that both sums coverge.

★ g. Show that for $S \subseteq \mathbb{Z}$, the following asymptotic bound does not necessarily hold, even assuming that both products coverge, by giving a counterexample:

$$\prod_{k \in S} \Theta\left( f(k) \right) = \Theta \left( \prod_{k \in S} f(k) \right) .$$

In both problems, it is assumed that $f(n)$ is an asymptotically positive function.

My attempt:

On page 58, in the Asymptotic notation in equation and inequalities section, the authors write:

The number of anonymous functions in an expression is understood to be equal to the number of times the asymptotic notation appears.

They also write, regarding the interpretation of asymptotic notation in an equation:

No matter how the anonymous functions are chosen on the left of the equal sign, there is a way to choose the anonymous functions on the right of the equal sign to make the equation valid.

Based on these two rules my understanding of problem f is that for any function $g(k)$ which is $\Theta(f(k))$, I need to prove that the quotient $$\frac{\sum_{k \in S} g(k)}{\sum_{k \in S} f(k)} $$ is asymptotically bounded.

I am, however, unhappy with this formulation. In the right-hand side, for any fixed set $S$, the sum $\sum_{k \in S} f(k)$ is a constant. Similarly, the left-hand side appears to me to be constant too.

As a question in asymptotics, I'm looking for a variable to take the limit over and limit point. However, $k$ is "summed out" over $S$, and I cannot see to make sense of the problem.

One other way I tried to interpret the problem is that $S$ is a variable set $S_n$, for instance $S_n=\{1,2,\dots,n\}$. Then with a function such as $f(k)=k$ the equation becomes $$ \sum_{k=1}^n \Theta(k) = \Theta \left(\frac{n(n+1)}{2} \right) = \Theta \left( n^2 \right), $$ which appears reasonable.

Unfortunately, I am unhappy with this interpretation too. Why not include sets parametrized by two variables $S_{m,n}$ then? Or even many more? In that case the problem seems to get more difficult.

---

In summary, I would greatly appreciate help in breaking down the two problems into a more clearly posed form.

Thanks.

Edit:

A further complication for me is interpreting the $\Theta$ notation of the left-hand sides. Does the anonymous function $g(k) = \Theta(f(k))$ imply the limit is taken as $k \to \infty$ or as $k \to -\infty$? or both? With $S \subseteq \mathbb{Z}$ either limit is possible.

Answer 1

Here is one way to interpret and solve the problems.

First, I will rely on page 55, where the authors write

... We therefore assume that every function used within $O$-notation is asymptotically nonnegative. This assumption holds for the other asymptotic notations defined in this chapter as well.

Second, as I mention in my question I interpret the question as

$$\sum_{k \in S_n} g(k) \in \Theta\left( \sum_{k \in S_n} f(k) \right),$$ with $S_n$ a sequence of subsets of $\mathbb{Z}$, $g(\cdot)$ being the anonymous function of the left-hand side $\Theta$-notation and the asymptoticity applying as $|k| \to \infty$ for $g(k) \in \Theta(f(k))$ and as $n \to +\infty$ for the right-hand side.

As $g(k) \in \Theta(f(k))$, there exists positive constants $k_0,c_1,c_2$ such that whenever $|k| \geq k_0$ we have $$0 \leq c_1 f(k) \leq g(k) \leq c_2 f(k). $$

For any $n$ we then have $$ \begin{align} \sum_{k \in S_n} g(k) &= \sum_{k \in S_n \\|k| <k_0 } g(k) + \sum_{k \in S_n \\ |k| \geq k_0} g(k) \\ &\leq \sum_{k \in S_n \\|k| <k_0 } g(k) + c_2 \sum_{k \in S_n \\ |k| \geq k_0} f(k) \\ &= \sum_{k \in S_n \\|k| <k_0 } g(k) + c_2 \left( \sum_{k \in S_n \\ |k| \geq k_0} f(k) + \sum_{k \in S_n \\ |k| < k_0} f(k) - \sum_{k \in S_n \\ |k| < k_0} f(k) \right) \\ &=\sum_{k \in S_n \\|k| <k_0 } \left( g(k) - c_2 f(k) \right) + c_2 \sum_{k \in S_n} f(k). \end{align} $$

Since $k_0$ is fixed, the set $$A:=\left\{ \sum_{k \in S_n \\|k| <k_0 } \left( g(k) - c_2 f(k) \right): n \in \mathbb{N} \right\} $$ is finite, and thus admits a maximum $M=\max A$.

Using the maximum bound we get

$$\sum_{k \in S_n} g(k) \leq M + c_2\sum_{k \in S_n} f(k) $$

Next I will make one more assumption: The sequence $\left( \sum_{k \in S_n} f(k) \right)_{n \in \mathbb{N}}$ tends to infinity as $n$ grows large.

Under that assumption it is clear that $\sum_{k \in S_n} g(k) \in O \left( \sum_{k \in S_n} f(k) \right)$. It is not much different to get $\sum_{k \in S_n} g(k) \in \Omega \left( \sum_{k \in S_n} f(k) \right)$.

The above is for problem e. For problem f it is easy to get a counterexample with $S_n=\{1,\dots,n\}$, $f(k) \equiv 1$ and $g(k) \equiv 2$.

Answer 2

One counterexample.

If $$|S|<+\infty$$ then the equality holds, becase they are constants.

Otherwise, assume that $$ S = N = \{1, 2, 3, ..., n, ...\} \\ f(k) = 2k $$ then $$ \prod_{k \in S} \Theta(f(k)) = \prod_{k \in S} \Theta(2k) = \prod_{k \in S} \Theta(k) = \Theta(n!) $$ but $$ \Theta(\prod_{k \in S} f(k)) = \Theta(\prod_{k \in S} 2k) = \Theta(2^n n!) $$

note that: we can not use the min and max function when there are infinitive elements in one set.