Master-theorem Method(老大定理)

• Master theorem && Example of Time Complexity

1. 
   \( \exists \varepsilon ( \underline{(\varepsilon> 0)}\wedge \underline{f(n)=O(n^{\log_{b}a-\varepsilon})} \rightarrow \underline{T(n)=\Theta(n^{\log_{b} a})} ) \)
2. 
   \( \forall k ( \underline{(k\geq 0)}\wedge \underline{f(n)=\Theta(n^{\log_{b} a}\lg^k n)} \rightarrow \underline{T(n)=\Theta(n^{\log_b a}\lg^{k+1}n)} ) \)
3. 
   \( \exists\epsilon\exists c ( \underline{(\epsilon > 0)}\wedge\underline{(c < 1)}\wedge \underline{f(n)=\Omega(n^{\log_b a+\epsilon})} \wedge \underline{a\times f(\frac{n}{b})\leq cf(n)} \rightarrow \underline{T(n)=\Theta(f(n))} ) \)

1. \( (n^{\log_b a} \) \( \;/\; \) \( f(n)) \) \( \geq \) \( n^{\epsilon} \)
2. \( ( f(n)\;/\; n^{\log_b a} ) \geq \lg^k n \)

   討論\( \lg^k n \)計算

   註解

   假設\( f(n)> n^{\log_ba} \) 那就可以用\( ( f(n)\;/\; n^{\log_b a} ) \geq \lg^k n \) 判斷，接著是判斷\( k \)是否\( \geq 0 \) \( ( f(n)\;/\; n^{\log_b a} ) = n^c,\; c> 0 \) \( \Rightarrow n^c=\lg^k n \) 取\( \log_{\lg n} \) \( \Rightarrow \log_{\lg n} n^c = \log_{\lg n} \lg^k n = \log_{\lg n} (\lg n)^k =k \) 討論\( \lg n \): \( n \)是一個很大的數\( \lg \)底數是2，那他的值一定會大於1，如果\( \log \)的底數是分數的話出來的值會是負數，就不符合\( k\geq 0 \) 改寫為 \( \log_{\lg n} (\frac{f(n)}{n^{\log_b a}})=k\geq 0 \) 判斷\( k \)值

   \( \forall n\forall c \)(\( (n\geq 1) \wedge (c>0) \) \( \rightarrow (n^c > 1)) \) \( \log_{\text{大於1的某數}}\text{大於1的某數}> 0 \)