

3.2 Standard notations and common functions

3.2-1

Show that if $f(n)$ and $g(n)$ are monotonically increasing functions, then so are the functions $f(n) + g(n)$ and $f(g(n))$, and if $f(n)$ and $g(n)$ are in addition nonnegative, then $f(n) \cdot g(n)$ is monotonically increasing.

$$ \begin{aligned} f(m) & \le f(n) \quad \text{ for } m \le n \\ g(m) & \le g(n) \quad \text{ for } m \le n, \\ \to f(m) + g(m) & \le f(n) + g(n), \end{aligned} $$

which proves the first function.

Then

$$f(g(m)) \le f(g(n)) \text{ for } m \le n.$$

This is true, since $g(m) > g(n)$ and $f(n)$ is monotonically increasing.

If both functions are nonnegative, then we can multiply the two equalities and we get

$$f(m) \cdot g(m) \le f(n) \cdot g(n).$$

3.2-2

Prove equation $\text{(3.16)}$.

$$ \begin{aligned} a^{\log_b c} = a^\frac{\log_a c}{\log_a b} = (a^{\log_a c})^{\frac{1}{\log_a b}} = c^{\log_b a} \end{aligned} $$

3.2-3

Prove equation $\text{(3.19)}$. Also prove that $n \ne \omega(2^n)$ and $n \ne o(n^n)$.

$$\lg(n!) = \Theta(n\lg n) \tag{3.19}$$

We use Stirling's approximation:

$$ \begin{aligned} \lg(n!) & = \lg\Bigg(\sqrt{2\pi n}\Big(\frac{n}{e}\Big)^n\Big(1 + \Theta(\frac{1}{n})\Big)\Bigg) \\ & = \lg\sqrt{2\pi n } + \lg\Big(\frac{n}{e}\Big)^n + \lg\Big(1+\Theta(\frac{1}{n})\Big) \\ & = \Theta(\sqrt n) + n\lg{\frac{n}{e}} + \lg\Big(\Theta(1) + \Theta(\frac{1}{n})\Big) \\ & = \Theta(\sqrt n) + \Theta(n\lg n) + \Theta(\frac{1}{n}) \\ & = \Theta(n\lg n). \end{aligned} $$

The other two are

$$\forall n > 3: 2^n = \underbrace{2 \cdot 2 \cdot \cdots \cdot 2}_\text{n times} < 1 \cdot 2 \cdot \cdots \cdot n = n! \quad \Rightarrow \quad n! = \omega(2^n).$$

and

$$\forall n > 1 : n! = 1 \cdot 2 \cdot \cdots n < \underbrace{n \cdot n \cdot \cdots \cdot n}_\text{n times} = n^n \quad \Rightarrow \quad n! = o(n^n).$$

3.2-4 $\star$

Is the function $\lceil \lg n \rceil!$ polynomially bounded? Is the function $\lceil \lg\lg n \rceil!$ polynomially bounded?

$\lceil \lg n \rceil!$ is not polynomially bounded, but $\lceil \lg\lg n \rceil!$ is.

Proving that a function $f(n)$ is polynomially bounded is equivalent to proving that $\lg(f(n)) = O(\lg n)$ for the following reasons.

• If $f$ is polynomially bounded, then there exist constants $c$, $k$, $n_0$ such that for all $n \ge n_0$, $f(n) \le cn^k$. Hence, $\lg(f(n)) \le kc\lg n$, which, since $c$ and $k$ are constants, means that $\lg(f(n)) = O(\lg n)$.
• Similarly, if $\lg(f(n)) = O(\lg n)$, then $f$ is polynomially bounded.

In the following proofs, we will make use of the following two facts:

1. $\lg(n!) = \Theta(n\lg n)$ (by equation $\text{(3.19)}$).
2. $\lceil \lg n \rceil = \Theta(\lg n)$, because
   • $\lceil \lg n \rceil \ge \lg n$
   • $\lceil \lg n \rceil < \lg n + 1 \le 2\lg n \text{ for all } n \ge 2$

$$ \begin{aligned} \lg(\lceil \lg n \rceil!) & = \Theta(\lceil \lg n \rceil \lg \lceil \lg n \rceil) \\ & = \Theta(\lg n\lg\lg n) \\ & = \omega(\lg n). \end{aligned} $$

Therefore, $\lg(\lceil \lg n \rceil!) \ne O(\lg n)$, and so $\lceil \lg n \rceil!$ is not polynomially bounded.

$$ \begin{aligned} \lg(\lceil \lg\lg n \rceil!) & = \Theta(\lceil \lg\lg n \rceil \lg \lceil \lg\lg n \rceil) \\ & = \Theta(\lg\lg n\lg\lg\lg n) \\ & = o((\lg\lg n)^2) \\ & = o(\lg^2(\lg n)) \\ & = o(\lg n). \end{aligned} $$

The last step above follows from the property that any polylogarithmic function grows more slowly than any positive polynomial function, i.e., that for constants $a, b > 0$, we have $\lg^b = o(n^a)$. Substitute $\lg n$ for $n$, $2$ for $b$, and $1$ for $a$, giving $\lg^2(\lg n) = o(\lg n)$.

Therefore, $\lg(\lceil \lg\lg n \rceil!) = O(\lg n)$, and so $\lceil \lg\lg n \rceil!$ is polynomially bounded.

3.2-5 $\star$

Which is asymptotically larger: $\lg(\lg^*n)$ or $\lg^*(\lg n)$?

$\lg^*(\lg n)$ is asymptotically larger because $\lg^*(\lg n) = \lg^*n - 1$.

3.2-6

Show that the golden ratio $\phi$ and its conjugate $\hat \phi$ both satisfy the equation $x^2 = x + 1$.

$$ \begin{aligned} \phi^2 - \phi - 1 & = \big(\frac{1 + \sqrt 5}{2}\big)^2 - \frac{1 + \sqrt 5}{2} - 1 \\ & = \frac{1 + 2\sqrt 5 + 5 - 2 - 2\sqrt 5 - 4}{4} \\ & = 0. \end{aligned} $$

$$ \begin{aligned} \hat\phi^2 - \hat\phi - 1 & = \big(\frac{1 - \sqrt 5}{2}\big)^2 - \frac{1 - \sqrt 5}{2} - 1 \\ & = \frac{1 - 2\sqrt 5 + 5 - 2 + 2\sqrt 5 - 4}{4} \\ & = 0. \end{aligned} $$

3.2-7

Prove by induction that the $i$th Fibonacci number satisfies the equality

$$F_i = \frac{\phi^i - \hat\phi^i}{\sqrt 5},$$

where $\phi$ is the golden ratio and $\hat\phi$ is its conjugate.

We have two base cases: $i = 0$ and $i = 1$. For $i = 0$, we have

$$ \begin{aligned} \frac{\phi^0 - \hat\phi^0}{\sqrt 5} & = \frac{1 - 1}{\sqrt 5} \\ & = 0 \\ & = F_0, \end{aligned} $$

and for $i = 1$, we have

$$ \begin{aligned} \frac{\phi^1 - \hat\phi^1}{\sqrt 5} & = \frac{(1 + \sqrt 5) - (1 - \sqrt 5)}{2\sqrt 5} \\ & = \frac{2\sqrt 5}{2\sqrt 5} \\ & = 1 \\ & = F_1. \end{aligned} $$

For the inductive case, the inductive hypothesis is that $F_{i - 1} = (\phi^{i - 1} - \hat\phi^{i - 1}) / \sqrt 5$ and $F_{i - 2} = (\phi^{i - 2} - \hat\phi^{i - 2}) / \sqrt 5$. We have

$$ \begin{aligned} F_i & = F_{i - 1} + F_{i - 2} & \text{(equation (3.22)} \\ & = \frac{\phi^{i - 1} - \hat\phi^{i - 1}}{\sqrt 5} + \frac{\phi^{i - 2} - \hat\phi^{i - 2}}{\sqrt 5} & \text{(inductive hypothesis)} \\ & = \frac{\phi^{i - 2}(\phi + 1) - \hat\phi^{i - 2}(\hat\phi + 1)}{\sqrt 5} \\ & = \frac{\phi^{i - 2}\phi^2 - \hat\phi^{i - 2}\hat\phi^2}{\sqrt 5} & \text{(Exercise 3.2-6)} \\ & = \frac{\phi^i - \hat\phi^i}{\sqrt 5}. \end{aligned} $$

3.2-8

Show that $k\ln k = \Theta(n)$ implies $k = \Theta(n / \ln n)$.

From the symmetry of $\Theta$,

$$k\ln k = \Theta(n) \Rightarrow n = \Theta(k\ln k).$$

Let's find $\ln n$,

$$\ln n = \Theta(\ln(k\ln k)) = \Theta(\ln k + \ln\ln k) = \Theta(\ln k).$$

Let's divide the two,

$$\frac{n}{\ln n} = \frac{\Theta(k\ln k)}{\Theta(\ln k)} = \Theta\Big({\frac{k\ln k}{\ln k}}\Big) = \Theta(k).$$