Master Theorem on Recursion

Given $$T[n]=\sum a_i T[n/b_i]+f(n),\quad a_i>0, b_i>1,$$ we want to find asymptotic expression for $T[n]$

# Critical exponent for $f=0$

When $f(n)=0$, we make the hypothesis that $T[n]=an^c_0$. From recursion formula, we find $\sum a_i/b_i^{c_0}=1$

# Case $f(n)\leq kn^{c}, c<c_0$

Define $$A=k\big/\Big[\sum a_i/b_i^c-1\Big]>0,\quad S[n]=T[n]+An^c$$ We have $$S[n]=\sum a_i S[n/b_i]$$

From our $f=0$ case analysis, $S[n]=\Theta(n^{c_0}), T[n]=\Theta(n^{c_0})-An^c=\Theta(n^{c_0})$

# Case $f(n)\geq kn^c, c>c_0$

Define $$B=-A=k\big/\Big[1-\sum a_i/b_i^c\Big]>0,\quad S[n]=T[n]-Bn^c$$ We have $$S[n]=\sum a_i S[n/b_i]$$

From our $f=0$ case analysis, $S[n]=\Theta(n^{c_0})$, $T[n]=\Theta(n^{c_0})+Bn^c=\Theta(n^c)$

# Case $f(n)=kn^{c_0}\log^k n, k\geq 0 $

Use ansatz $T[n]=kn^{c_0}\log^{k+1} n$, we find $T[n]-\sum a_i T[n/b_i]=\Theta(n^{c_0}\log^k n)$. So the ansatz is the correct solution.