Solving Recurrence Relations Using Master Theorem/Akra-Bazzi

[vapatel]

first state whether it can be solved using the Master Theorem, and if it can then use that. Otherwise, use the Akra-Bazzi formula.

1. T(n) = 3T([n/3])+n

2. T(n) = T([n/4])+T([n/3])+n

3. T(n) = 2T([n/4])+√n

 

[HallsofIvy]

Okay, what is the "master theorem" and what is the "Akra-Bazzi theorem"?