CLRS 연습문제 4.5

4.5-1

a. $\Theta\left(n^{\log _{4} 2}\right)=\Theta(\sqrt{n})$

b. $\Theta\left(n^{\log _{4} 2} \lg n\right)=\Theta(\sqrt{n} \lg n)$

c. $\Theta(n)$

d. $\Theta\left(n^{2}\right)$

4.5-3

$\begin{aligned} a & =1, b=2, \\ f(n) & =\Theta\left(n^{\lg 1}\right)=\Theta(1), \\ T(n) & =\Theta(\lg n) . \end{aligned}$