特殊的函數

$(\log n)^{\log n}$

$\Rightarrow n^{\log \log n} \\ 令 \;d \;為一常數\\ \because d\times \log n < \log \log n\times \log n \\ \log \log n \times \log n< \log n \times \log n \\ \log n \times \log n < n \\ n < n \times \log 2 \\ \therefore n^{\log \log n} > n^d \\ n^{\log \log n} < 2^n$

$(\log n)!$

$\because n! \approx n^{n+\frac{1}{2}} \cdot e^{-n} \quad(Stirling \;approximation)\\ \therefore (\log n)! \approx (\log n)^{\log n + \frac 12}\cdot e^{-\log n} \\ \Rightarrow (\log n)^{\log n + \frac 12}\cdot n^{-\log e} \\ \Rightarrow (\log n)^{\log n + \frac 12}\cdot n^{-1} \\ \Rightarrow n^{\log \log n} \cdot (\log n)^{\frac12}\cdot n^{-1} \\ \therefore (\log n)! < (\log n)^{\log n}$

$n^{\frac {1}{\log n}}$

$\because n = 2^{\log n} \\ \therefore (2^{\log n})^{\frac{1}{\log n}} \Rightarrow 2^{\log n \cdot \frac{1}{\log n}} \\ \Rightarrow 2^1 = 2$

$2^{\sqrt{2 \log n}}$

$2 = n^{\frac{1}{\log n}} \\ \Rightarrow n ^{\frac{\sqrt{2\log n}}{\log n}} \\ \because 0 < \frac{\sqrt{2\log n}}{\log n} < 1 \\ \therefore \log n < n^{\frac{\sqrt{2\log n}}{\log n}} < n^c, \forall c \in Z^+ , c \geq 1$

$(\log \log n)!$

f(n) log f(n)

n! $n\log n \notin O(\log n)$

$2^n$ $n\log 2 \notin O(\log n)$

$(\log n)!$ $(\log n)\cdot \log \log n \notin O(\log n)$

$n^2$ $2\log n \in O(\log n)$

$\log n$ $\log \log n \in O(\log n)$

$2^4$ $4\log 2 \in O(\log n)$

$\Rightarrow$ f(n) 為「Polynominal bound」 $\Leftrightarrow$ $\log f(n) \in O(\log n)$

f(n)	log f(n)
n!	$n\log n \notin O(\log n)$
$2^n$	$n\log 2 \notin O(\log n)$
$(\log n)!$	$(\log n)\cdot \log \log n \notin O(\log n)$
$n^2$	$2\log n \in O(\log n)$
$\log n$	$\log \log n \in O(\log n)$
$2^4$	$4\log 2 \in O(\log n)$

$\Rightarrow \log((\log \log n)!) = (\log \log n)\cdot(\log \log \log n) \\ \Rightarrow (\log \log n)\cdot(\log \log \log n) \leq (\log \log n)^2 \\ \Rightarrow (\log \log n)\cdot(\log \log \log n) = O(\log n) \\ \therefore (\log \log n)! \;為\;「Polynominal \;bound」$