Give upper and lower bounds for Tn 8Tn3n2log5n using master

Give upper and lower() bounds for T(n)= 8T(n/3)+(n²log⁵n) using master method.

Solution

Master theorem.

Suppose that T(n) is a function on the nonnegative integers that satisfies the recurrence where n / b means either n / b or n / b. Let k = logb a. Then,

Case 1. If f(n) = O(n^{k –} ) for some constant > 0, then T (n) = (n^k).

Case 2. If f(n) = (n^k log ^p n), then T (n) = (n^k log ^p+1 n).

Case 3. If f(n) = (n^{k +} ) for some constant > 0 and if a f(n / b) c f (n) for some constant c < 1 and all sufficiently large n, then T (n) = ( f(n) ).

The given problem fits to case 2 as f(n) is in the form (n^k log ^p n) where k=2 and p=5

Thus, T (n) = (n² log ⁶ n)