Give upper and lower bounds for Tn8Tn4n2 using the master me

Give upper and lower() bounds for T(n)=8T(n/4)+n² using the master method.

Solution

T(n) = 8T(n/2) + cn², where c is some positive constant. We see that this has the appropriate form for applying the master method, and that a=8, b=2, and h(n) = cn². cn² is O(n^log₂8 ) = O(n³ ) for any 1, so this falls into case 1. Therefore, T(n) is (n³).

case 1: h(n) is O(n^log_ba ), which says that h grows more slowly than the number of leaves. In this case, the total work is dominated by the work done at the leaves, so T(n) is(n^log_ba).