需要幫助的證明了這一點認識主定理

Question

我真的很感激，如果有人可以幫助我幾個問題，

以下的每一個遞歸函數的定義，用主定理來確定其生長的漸近階（即Big-Tetha）。如果你認爲大師定理不適用於某個特定情況，那麼應該正確解釋原因。在這些情況下，您仍然可以爲運行時間提供一個合理的上限（即Big-O）嗎？請注意，基本情況都假定爲常量。

的（a）T（N）= T（N/2）+ 2^N

（B）T（N）= 4T（N/2）+（N^1.5） - 1

（C）T（N）= T（N/3）+ 100

（d）是T（N）= 125T（N/5）+ N^3/LOGN

（e）中T（n）= 2T（n/7）+ log n +√n

我剛剛在網上閱讀了一些關於此的東西，我無法獲得足夠的理解來回答這個問題。任何幫助將不勝感激，我正在努力學習測試，我沒有得到任何這樣的！

非常感謝！

Answer 1

除（a）以外的所有項目都可以使用馬斯特定理。在情況（a）中，收費函數不是多項式，因此主定理不適用。但可以通過擴張解決它：

T(n) = 2^n + T(n/2) 
    = 2^n + 2^(n/2) + T(n/4) 
    = 2^n + 2^(n/2) + 2^(n/4) + T(n/8) 
    = ... 
    = O(2^n). 

結果是通過intepreting復發作爲二進制數的總和明顯：1 + 10 + 100 + 10000 +千萬< = 2 * 10000000。