Chapter 3

Exercise 3.1-1

Available in the latest revision of the IM.

Exercise 3.1-2

Available in the latest revision of the IM.

Exercise 3.1-3

Available in the latest revision of the IM.

Exercise 3.2-1

Available in the latest revision of the IM.

Exercise 3.2-2

Available in the latest revision of the IM.

Exercise 3.2-4

Available in the latest revision of the IM.

Exercise 3.2-5

Available in the latest revision of the IM.

Exercise 3.2-6

Available in the latest revision of the IM.

Exercise 3.2-7

Available in the latest revision of the IM.

Exercise 3.3-1

Let $m \le n$. This implies that $f(m) \le f(n)$ and $g(m) \le g(n)$.

If we add up these inequalities, then we get $f(m)+g(m)\le f(n)+g(n)$, thus proving that $f(n)+g(n)$ is monotonically increasing. If we multiply these inequalities, provided that both $f$ and $g$ are nonnegative, then we get $f(m) \cdot g(m)\le f(n) \cdot g(n)$, thus proving that $f(n) \cdot g(n)$ is monotonically increasing.

By definition $f(g(m)) \le f(g(n))$, so the composition $f(g(n))$ is also monotonically increasing.

Exercise 3.3-2

Available in the latest revision of the IM.

Exercise 3.3-3

$f(n)=o(n)$ implies that $0 \le f(n) < cn$ for all $c >0$ and $n \ge n_0$. For $n \ge n_0$ we have$n \le n + f(n) < (1+c)n$, thus $n+o(n)=\Theta(n)$, since we can choose any constant greater than 1 for the upper bound. Consequently, $(n+o(n))^k=(\Theta(n))^k=\Theta(n^k)$ for any real $k$. As a side note, if $k <0$, then the inequalities of $\Theta$ are reverse of those when $k>0$.

Analogously, we can prove that $n-o(n)=\Theta(n)$ by simply reversing inequalities $n \ge n-f(n)>(1-c)n$ and choosing any positive constant less than 1 for the lower bound.

$\lceil n\rceil=n+o(n)$, so $\lceil n\rceil^k=\Theta(n^k)$. $\lfloor n\rfloor=n-o(n)$, so $\lfloor n\rfloor^k=\Theta(n^k)$.

Exercise 3.3-4

a.

$$\begin{align*} a^{\log_b c} &= a^{\frac {\log_a c}{\log_a b}} && \text{(by equation (3.19))} \\ &= c^{\frac {1}{\log_a b}} && \text{(by equation (3.17))} \\ &= c^{\log_b a} \end{align*}$$

b.

$$\frac {n!}{n^n}=\frac{1}{n} \cdot \frac{2}{n} \dots \frac{n}{n} \implies \lim_{n \to \infin} \frac{n!}{n^n}=0$$

Observe that the largest term on the right side is 1, whilst the initial terms tend to zero as n increases. Therefore, $n!=o(n^n)$.

$$\frac {n!}{2^n}=\frac{1}{2} \cdot \frac{2}{2} \dots \frac{n}{2} \implies \lim_{n \to \infin} \frac{n!}{2^n}=\infin$$

Here, we have an opposite situation, thus $n!=\omega(2^n)$.

A weak upper bound on the factorial function is $n! \le n^n$, so $\lg n! \le n\lg n$. This establishes an upper bound $\lg n!=O(n\lg n)$.

$$\begin{align*} \lg n! &= \lg {(\sqrt{2\pi n}\,(n/e)^n e^{\alpha_n})} && \text{(by equation (3.29))} \\ &> \lg {(n/e)^n} \\ &> \lg {(\sqrt n)^n} && \text{(} e < \sqrt n \text{ when } n \ge 9 \text{)} \\ &= \frac {n \lg n}{2} \\ &\therefore \lg n! = \Omega(n \lg n) \end{align*}$$

Theorem 3.1 implies that $\lg n!=\Theta(n\lg n)$.

c.

Let $f(n)=\Theta(n)$. By definition $c_1n \le f(n) \le c_2n$ for some positive constants and $n \ge n_0$.

$$\begin{align*} \lg f(n) &\ge \lg c_1n \\ &=\lg c_1 + \lg n \\ &\ge \lg \frac{1}{\sqrt n} + \lg n && \text{(when } n \ge 1/c_1^2 \text{)} \\ &= \lg \sqrt n \\ &= \frac {\lg n}{2} \\ &\therefore \lg f(n) = \Omega(\lg n) \end{align*}$$

$$\begin{align*} \lg f(n) &\le \lg c_2n \\ &=\lg c_2 + \lg n \\ &\le 2\lg n && \text{(when } n \ge c_2 \text{)} \\ &\therefore \lg f(n) = O(\lg n) \end{align*}$$

Theorem 3.1 implies that $\lg f(n)=\Theta(\lg n)$ for all $n \ge \max\{n_0,1/c_1^2,c_2\}$. This concludes the proof.

Exercise 3.3-5

Available in the latest revision of the IM.

Exercise 3.3-6

Available in the latest revision of the IM.

Exercise 3.3-7

Available in the latest revision of the IM.

Exercise 3.3-8

Available in the latest revision of the IM.

Exercise 3.3-9

Available in the latest revision of the IM.

Problem 3-1

In all subproblems, we rely on the fact, stated in the book on page 65, that for an asymptotically positive polynomial $p(n)$ of degree $d$, we have $p(n)=\Theta(n^d)$. Consequently, for some positive constants it holds that $0 \le c_1n^d \le p(n) \le c_2n^d$ for all $n \ge n_0$.

a.

$n^k \ge n^d$ for all $n \ge 1$, so $0 \le p(n) \le c_2n^d \le c_2n^k$ for all $n \ge n_0$. Thus, $p(n)=O(n^k)$.

b.

$n^k \le n^d$ for all $n \ge 1$, so $0 \le c_1n^k \le c_1n^d \le p(n)$ for all $n \ge n_0$. Thus, $p(n)=\Omega(n^k)$.

c.

$k=d$ means that $k \ge d \land k \le d$, so parts (a) and (b) apply. Theorem 3.1 implies that $p(n)=\Theta(n^k)$.

d.

We fix a positive constant $c$ and show that for sufficiently large $n$ it is true that $c_2n^d < cn^k$. We can rewrite this inequality as $c_2/c < n^{k-d}$. Apparently, it holds for all $n > (c_2/c)^{1/(k-d)}$. Choosing $n$ to be greater than this value and $n_0$ ensures that $0\le p(n)\le c_2n^d<cn^k$. As the choice of $c$ was arbitrary the derivation applies to all positive constants, hence $p(n)=o(n^k)$.

e.

We fix a positive constant $c$ and show that for sufficiently large $n$ it is true that $c_1n^d > cn^k$. We can rewrite this inequality as $c/c_1 < n^{d-k}$. Apparently, it holds for all $n > (c/c_1)^{1/(d-k)}$. Choosing $n$ to be greater than this value and $n_0$ ensures that $0\le cn^k < c_1n^d \le p(n)$. As the choice of $c$ was arbitrary the derivation applies to all positive constants, hence $p(n)=\omega(n^k)$.

Problem 3-2

Available in the latest revision of the IM.

Problem 3-3

Available in the latest revision of the IM.

Problem 3-4

Available in the latest revision of the IM.

Problem 3-5

Assume that all constants introduced in the subproblems are positive. Furthermore, we proceed from left to right in all identities.

a.

Let $g(n)=\Theta(f(n))$, thus $0 \le c_1f(n) \le g(n) \le c_2f(n)$ for all $n \ge n_g$. Let $h(n)=\Theta(g(n))$, so $0 \le d_1g(n) \le h(n) \le d_2g(n)$ for all $n \ge n_h$. Substituting $g(n)$ with $f(n)$ we get $0 \le c_1d_1f(n) \le h(n) \le c_2d_2f(n)$ for all $n \ge \max\{n_g,n_h\}$. Therefore, $h(n)=\Theta(f(n))$, which concludes the proof.

b.

Let $g(n)=\Theta(f(n))$, thus $0 \le c_1f(n) \le g(n) \le c_2f(n)$ for all $n \ge n_g$. Let $h(n)=O(f(n))$, so $0 \le h(n) \le df(n)$ for all $n \ge n_h$. By combining these inequalities we get for all $n \ge \max\{n_g,n_h\}$

$$0 \le c_1f(n) \le g(n)+h(n) \le (c_2+d)f(n)$$

Therefore, $g(n)+h(n)=\Theta(f(n))$, which concludes the proof.

c.

Let $h(n)=\Theta(f(n))$, thus $0 \le c_1f(n) \le h(n) \le c_2f(n)$ for all $n \ge n_h$. Let $q(n)=\Theta(g(n))$, so $0 \le d_1g(n) \le q(n) \le d_2g(n)$ for all $n \ge n_q$. Adding together these inequalities we get for all $n \ge \max\{n_h,n_q\}$

$$0 \le \min\{c_1,d_1\}(f(n) +g(n))\le h(n) +q(n)\le 2\max\{c_2,d_2\}(f(n) +g(n))$$

Therefore, $h(n)+q(n)=\Theta(f(n)+g(n))$, which concludes the proof.

d.

Let $h(n)=\Theta(f(n))$, thus $0 \le c_1f(n) \le h(n) \le c_2f(n)$ for all $n \ge n_h$. Let $q(n)=\Theta(g(n))$, so $0 \le d_1g(n) \le q(n) \le d_2g(n)$ for all $n \ge n_q$. Multiplying together these inequalities we get for all $n \ge \max\{n_h,n_q\}$

$$0 \le c_1d_1(f(n) \cdot g(n)) \le h(n) \cdot q(n) \le c_2d_2(f(n) \cdot g(n))$$

Therefore, $h(n) \cdot q(n)=\Theta(f(n) \cdot g(n))$, which concludes the proof.

e.

$$\begin{align*} (a_1n)^{k_1} \lg^{k_2} (a_2n) &= a_1^{k_1}n^{k_1} (\lg n + \lg a_2)^{k_2} \\ &= \Theta(a_1^{k_1}n^{k_1}) (\lg n + o(\lg n))^{k_2} && \text{(by reflexivity)} \\ &= \Theta(n^{k_1}) \cdot \Theta(\lg^{k_2} n) && \text{(by Problem 3-4 part (h))} \\ &= \Theta(n^{k_1}\lg^{k_2} n) && \text{(by part (d))} \end{align*}$$

Problem 3-6

a.

If $f(n)=O(g(n))$ or $f(n)=\Omega(g(n))$, then we are done. Observe that $f(n)=\Omega(g(n))$ implies $f(n)=\overset{\infty}{\Omega}(g(n)).$

Pick any positive constant $c$. There must be infinitely many points where $f(n) > cg(n)$, otherwise we could find a positive threshold $n_0$ such that $f(n) \le cg(n)$ for all $n \ge n_0$. In other words, for any $n_0$ there is some $m>n_0$ where $f(m) >cg(m)$. Consequently, $f(n)=\overset{\infty}{\Omega}(g(n)).$

b.

See Problem 3-2 part (c).

c.

As shown in part (a), one advantage of using omega infinity over standard omega is that all asymptotically nonnegative functions become asymptotically comparable. On the other hand, from omega infinity we cannot deduce that one function is "larger" than the other. Oscillations are permitted. Furthermore, we don't know anything about how those infinitely many points are distributed. With classical omega notation it is clear that the condition holds for all $n \ge n_0$. Finally, omega infinity is rather an esoteric notation, unknown to most software engineers.

d.

$f(n)=\Theta(g(n))$ implies that $f(n)=|f(n)|$ is an asymptotically nonnegative function, thus $f(n)=O'(g(n))$ immediately follows from $f(n)=O(g(n))$. Therefore, the "only if" direction remains valid after the substitution.

$f(n)=\Omega(g(n))$ implies that $f(n)=|f(n)|$ is an asymptotically nonnegative function, thus $f(n)=O(g(n))$ immediately follows from $f(n)=O'(g(n))$. Therefore, the "if" direction also remains valid after the substitution.

e.

$$\begin{align*} \widetilde{\Omega}(g(n)) = \{f(n):\,{} & \text{there exist positive constants $c$, $k$, and $n_0$ such that} \\ & \text{$0 \le cg(n)\lg^kn \le f(n)$ for all $n \ge n_0$}\} \\[2mm] \widetilde{\Theta}(g(n)) = \{f(n):\,{} & \text{there exist positive constants $c_1$, $c_2$, $k_1$, $k_2$, and $n_0$ such that} \\ & \text{$0 \le c_1g(n)\lg^{k_1}n \le f(n) \le c_2g(n)\lg^{k_2}n$ for all $n \ge n_0$}\} \end{align*}$$

The proof of the corresponding analog to Theorem 3.1 is essentially the same as for the original version (see Exercise 3.2-4). The only difference is that we should use these new definitions.

Problem 3-7

Available in the latest revision of the IM.