Let Tn be defined by the recurrence formula Tn0 2 n 1 2 9

Let T(n) be defined by the recurrence formula. T(n0 = {2 n = 1, 2 9 T (n/s) +1 n lessthanorequalto3 show that n greaterthanorequalto s n - 1, and hence T9n) = O(n)

Solution

Answer :

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

Use Masters theorm , we have

a = 9 , b = 3 , c = 0

Now , n^loga base b = n^log9 base 3 = 2 = n^2

since c < n^loga base b , therefore T(n) = theta(n^loga base b ) => T(n) = theta(n^2)