請用A4紙張繳交



┌──────────────────────────────────┐
│ T(1)=1　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 │
│　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　│
│ T(n)=aT(n/b)+cn^i , n > 1　　　　　　　　　　　　　　　　　　　　　│
│　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　│
│ if a<b^i , T(n)=Θ(n^i)　　　　　　　　　　　　　　　　　　　　　　│
│　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　│
│ if a=b^i , T(n)=Θ(n^i * log_b(n) )　　　　　　　　　　　　　　　　│
│　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　│
│ if a>b^i , T(n)=Θ(n^log_b(a) )　                　　　　　　　　　│
└──────────────────────────────────┘

當 a<b^i 時  設 n=b^j

                   j-1
    T(n)=a^j+cb^ji Σ  (a/b^i)^k
                   k=0

        = ... = (n^i)c'


請用 a<b^i 的方法 推倒當 a>b^i 時 T(n)的最後化簡結果 & 過程