T(n)=aT(n/b)+f(n);
where we can interpret n/b to mean either floor(b/n) or ceil(b/n), Then T (n) has the following asymptotic bounds:
1. If f (n)= O(nlogb a-c) for some constant c> 0, then T (n)=Θ(nlogb a)
2.If f (n)= Θ(nlogb a), then T (n)=Θ(nlogb a log n)
3. If f (n)= Ω(nlogb a+c) for some constant c> 0, and if af (n/b)>= cf (n) for
some constant c < 1 and all sufficiently large n, then T (n)= Θ(f(n)).
//
comments：
compare the f(n) and b logb a,and the max will determine the complexity of the recurrence.
in case 1 and case 3 ,the larger determine the complexity of the recurrence,
in case 2,they are the same size ,so,there add a factor log n.
besides all the comparison must be polynomically smaller or larger.