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) \le 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 can use Stirling's approximation to prove these three equations.

For equation $\text{(3.19)}$,

$$ \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} $$

For $n! \ne \omega(2^n)$,

$$ \begin{aligned} \lim_{n \to \infty} \frac{2^n}{n!} & = \lim_{n \to \infty} \frac{2^n}{\sqrt{2\pi n} \left(\frac{n}{e}\right)^n \left(1 + \Theta\left(\frac{1}{n}\right)\right)} \\ & = \lim_{n \to \infty} \frac{1}{\sqrt{2\pi n} \left(1 + \Theta\left(\frac{1}{n}\right)\right)} \left(\frac{2e}{n}\right)^n \\ & \le \lim_{n \to \infty} \left(\frac{2e}{n}\right)^n \\ & \le \lim_{n \to \infty} \frac{1}{2^n} = 0, \end{aligned} $$

where the last step holds for $n > 4e$.

For $n! \ne o(n^n)$,

$$ \begin{aligned} \lim_{n \to \infty} \frac{n^n}{n!} & = \lim_{n \to \infty} \frac{n^n}{\sqrt{2\pi n} \left(\frac{n}{e}\right)^n \left(1 + \Theta\left(\frac{1}{n}\right)\right)} \\ & = \lim_{n \to \infty} \frac{e^n}{\sqrt{2\pi n} \left(1 + \Theta\left(\frac{1}{n}\right)\right)} \\ & = \lim_{n \to \infty} O(\frac{1}{\sqrt n})e^n \\ & \ge \lim_{n \to \infty} \frac{e^n}{c\sqrt n} & \text{(for some constant $c > 0$)}\\ & \ge \lim_{n \to \infty} \frac{e^n}{cn} \\ & = \lim_{n \to \infty} \frac{e^n}{c} = \infty. \end{aligned} $$

3.2-4 $\star$

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

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 means that $\lg(f(n)) = O(\lg n)$.
  • 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)$
  2. $\lceil \lg n \rceil = \Theta(\lg n)$

$\lceil \lg n \rceil!$ is not polynomially bounded because

$$ \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) \\ & \ne O(\lg n). \end{aligned} $$

$\lceil \lg\lg n \rceil!$ is polynomially bounded because

$$ \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) \\ & = 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)$?

We have $\lg^* 2^n = 1 + \lg^* n$,

$$ \begin{aligned} \lim_{n \to \infty} \frac{\lg(\lg^*n)}{\lg^*(\lg n)} & = \lim_{n \to \infty} \frac{\lg(\lg^* 2^n)}{\lg^*(\lg 2^n)} \\ & = \lim_{n \to \infty} \frac{\lg(1 + \lg^* n)}{\lg^* n} \\ & = \lim_{n \to \infty} \frac{\lg(1 + n)}{n} \\ & = \lim_{n \to \infty} \frac{1}{1 + n} \\ & = 0. \end{aligned} $$

Therefore, we have that $\lg^*(\lg n)$ is asymptotically larger.

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 & = \Bigg(\frac{1 + \sqrt 5}{2}\Bigg)^2 = \frac{6 + 2\sqrt 5}{4} = 1 + \frac{1 + \sqrt 5}{2} = 1 + \phi \\ \hat\phi^2 & = \Bigg(\frac{1 - \sqrt 5}{2}\Bigg)^2 = \frac{6 - 2\sqrt 5}{4} = 1 + \frac{1 - \sqrt 5}{2} = 1 + \hat\phi. \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.

  • Base case

    For $i = 0$,

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

    For $i = 1$,

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

  • Assume

    • $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$,

    $$ \begin{aligned} F_i & = F_{i - 1} + F_{i - 2} \\ & = \frac{\phi^{i - 1} - \hat\phi^{i - 1}}{\sqrt 5} + \frac{\phi^{i - 2} - \hat\phi^{i - 2}}{\sqrt 5} \\ & = \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} \\ & = \frac{\phi^i - \hat\phi^i}{\sqrt 5}. \end{aligned} $$

3.2-8

Show that $k\ln k = \Theta(n)$ implies $k = \Theta(n / \lg 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).$$