Type the master-recurrence form and its watershed function

Answer

T(n) = a*T(n/b) + f(n) watershed = n^(log_b a) compare f(n) to the watershed

Case 1 if f is polynomially smaller than the watershed (Θ of watershed); case 2 if they tie (add a log); case 3 if f is polynomially larger and regularity holds (Θ of f).