recursion - 相同的渐近增长 - 主定理

Question

给定主定理：

if a) f(1) = g(1) and b) f(n) = a f(n/b) + g(n),   
then:  
(1) f(n) ∈ Θ(n^c); if a < b^c  
(2) f(n) ∈ Θ(n^c * log n); if a = b^c  
(3) f(n) ∈ Θ(n ^ log b (a); if a > b^c

如何证明如果 h(x) 与 f(x) 具有相同的递推方程，但初始值不同，它们仍然具有相同的渐近增长？非常感谢！

标签： recursioncomplexity-theoryrecurrencemaster-theorem