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:

$\lg(n!) = \Theta(n\lg n)$
$\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 n = 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).\]

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用