CLRS 연습문제 3.2

3.2-1

첫 번째 함수는 $\begin{aligned} f(m) & \leq f(n) \quad \text { for } m \leq n \\ g(m) & \leq g(n) \quad \text { for } m \leq n, \\ \rightarrow f(m)+g(m) & \leq f(n)+g(n) \end{aligned}$
으로 증명되고, $f(n)$이 단조 증가하므로

$f(g(m)) \leq f(g(n)) \text { for } m \leq n \text {. }$이다.

두 함수 모두 음수가 아니므로 두 개의 부등식을 곱할 수 있다. 따라서 $f(m) \cdot g(m) \leq f(n) \cdot g(n) .$ 이다.

3.2-2

$a^{\log _{b} c}=a^{\frac{\log _{a} c}{\log _{a} b}}=\left(a^{\log _{a} c}\right)^{\frac{1}{\log _{a} b}}=c^{\log _{b} a}$

3.2-6

$\begin{array}{l} \phi^{2}=\left(\frac{1+\sqrt{5}}{2}\right)^{2}=\frac{6+2 \sqrt{5}}{4}=1+\frac{1+\sqrt{5}}{2}=1+\phi \\ \hat{\phi}^{2}=\left(\frac{1-\sqrt{5}}{2}\right)^{2}=\frac{6-2 \sqrt{5}}{4}=1+\frac{1-\sqrt{5}}{2}=1+\hat{\phi} . \end{array}$

3.2-8

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

$\ln n=\Theta(\ln (k \ln k))=\Theta(\ln k+\ln \ln k)=\Theta(\ln k)$이다. 둘을 나누면

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