How do you find the order of growth for the following recurr

How do you find the order of growth for the following recurrence?

T(n) = 9T(n/3) + n²

Solution

The Master Theorem applies to recurrences of the following form:
T (n) = aT (n/b) + f (n)
where a 1 and b > 1 are constants and f (n) is an asymptotically positive function.
There are 3 cases:

Case First:-- f(n) is O(nlogba ). Since the leaves grow faster than f, all work is done at the leaves, so T(n) is (nlogb a).

Case Second:-- f(n) is (nlogba). The leaves grow at same rate as f, so the same order of work is done at every level of tree. Therfore tree has O(log n) levels times the work done on one level, yielding T(n) is (nlogb a log n).

Case Third:-- f(n) is (nlogba + ). Here f grows faster than the number of leaves, which means that asymptotically the total amount of work is dominated by the work done at the root node. For the upper bound, we also need an extra smoothness condition on f in this case i.e af(n/b) cf(n) for some constant c < 1 and large n. In this case T(n) is (f(n)).

Therefore, using Master Method on your above Question

a=9, b=3, =log39 = 2, f(n) = n2, so Case 2, i.e. T(n) = (nlogn) = (n2logn).