3-5 Manipulating asymptotic notation

Let $f(n)$ and $g(n)$ be asymptotically positive functions. Prove the following identities: a. $\Theta(\Theta(f(n)))=\Theta(f(n))$.

b. $\Theta(f(n))+O(f(n))=\Theta(f(n))$.

c. $\Theta(f(n))+\Theta(g(n)) =\Theta(f(n)+g(n))$.

d. $\Theta(f(n))\cdot \Theta(g(n))=\Theta(f(n)\cdot g(n))$.

e. Argue that for any real constants $a_1,b_1>0$ and integer constants $k_1,k_2$, the following asymptotic bound holds:

$(a_1 n)^{k_1}\lg^{k_2}(a_2 n)=\Theta(n^{k_1}\lg^{k_2}n)$.

$\star$ f. Prove that for $S\subseteq \Z$, we have

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

assuming that both sums converge.

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

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

a

$$ \begin{aligned} g(n)=\Theta(f(n))\cr \implies c_1 f(n)\leq g(n) \leq c_2 f(n)\cr h(n)=\Theta(g(n))\cr \implies c_1 d_1 f(n)\leq d_1 g(n)\leq h(n)\leq d_2g(n)\leq c_2 d_2 f(n)\cr \implies h(n)=\Theta(f(n))\cr \implies\Theta(\Theta(f(n)))=\Theta(f(n))\cr \end{aligned} $$

b

$$ \begin{aligned} \forall g(n)=\Theta(f(n)) \And h(n)=\Theta(f(n))\cr \implies c_2 f(n) \leq g(n)\leq c_1 f(n) \And 0 \leq h(n)\leq df(n)\cr \implies c_1f(n)\leq g(n)+h(n)\leq (c_1+d)f(n)\cr \implies g(n)+h(n)=\Theta(f(n))\cr \implies \Theta(f(n))+O(f(n))=\Theta(f(n))\cr \end{aligned} $$

c

$$ \begin{aligned} \forall A(n)=\Theta(f(n))\And B(n)=\Theta(g(n))\cr \implies c_1 f(n)\leq A(n)\leq c_2 f(n)\And d_1 f(n)\leq B(n) \leq d_2 f(n)\cr \implies \min(c_1,d_1)(f(n)+g(n))\leq A(n)+B(n)\leq \max(c_2+d_2)(f(n)+g(n))\cr \implies \Theta(f(n))+\Theta(g(n)) =\Theta(f(n)+g(n)) \end{aligned} $$

d

$$ \begin{aligned} \forall A(n)=\Theta(f(n))\And B(n)=\Theta(g(n))\cr \implies c_1 f(n)\leq A(n)\leq c_2 f(n)\And d_1 f(n)\leq B(n) \leq d_2 f(n)\cr \implies c_1 d_1f(n)\cdot g(n)\leq A(n)\cdot B(n)\leq c_2 d_2f(n)\cdot g(n)\cr \implies \Theta(f(n))\cdot \Theta(g(n)) =\Theta(f(n)\cdot g(n)) \end{aligned} $$

e

$$ \begin{aligned} \text{we only need to prove: }c_1 n^{k_1}\lg^{k_2}n\leq (a_1 n)^{k_1}\lg^{k_2}(a_2 n)\leq c_2 n^{k_1}\lg^{k_2}n\cr \text{which is implied by: }d_1 lg^{k_2}n\leq\lg^{k_2}(a_2 n)\leq d_2\lg^{k_2}n\cr \text{which is implied by: }e_1\lg n\leq \lg a+\lg n \leq e_2 \lg n\cr \text{which is implied by: }e_1\leq \lg a/\lg n +1 \leq e_2\cr \text{choose }e_1=1/2 \quad e_2=2 \quad n_0=\lg max(a^2,2^{\lg a}) \text{ satisfies}\cr \end{aligned} $$

$\star$ f

$$ \begin{aligned} g(k)=\Theta(f(k))\cr \implies \sum_{k\in S} c_kf(k)\leq \sum_{k\in S} g(k)\leq \sum_{k\in S} d_kf(k)\cr \implies \min( c_k) \sum_{k\in S} f(k)\leq \sum_{k\in S} g(k)\leq \max(d_k)\sum_{k\in S} f(k)\cr \implies \sum_{k\in S}\Theta(f(k))=\Theta(\sum_{k\in S}f(k))\cr \end{aligned} $$

$\star$ g

$\prod_{k\in S} \frac 1 2=\prod_{k\in S} \Theta(\frac{1}{2^n})=\Theta(0)\neq \Theta(\prod_{k\in S} 1)=\Theta(1)$