What would be the efficiency class of the algorithm based on the master theorem? ROBE. The master theorem is as follows T(n) = at(n/b) + f(n) where f(n) (n"), k20 If a bk, T(n) (nlogga) Decrease-by-a-constant-factor recurrences The Master Theorem T(n) = aT(n/b) + f(n), k>=0 where f(n) O(nk), 1. a bk T(n) O(nk) T(n) e O(nk log n ) T(n) e O(nlogba) Examples: - T(n) = (n/2) + 1 - T(n) = 2T(n/2) + n2 - T(n) = 3 T(n/2) + n (logn) (n2) (nlog23)