Recurrence Assuming in each case that Tn is eventually nonde

Recurrence

Assuming in each case that T(n) is eventually nondecreasing, use Theorem B.5 to determine the order of the following recurrence equations. T(n) = 2T(n/5) + 6n^3 for n > 1, n a power of 5 T(1) = 6 T(n) = 40T(n/3) + 2n^3 for n > 1, n a power of 3 T(1) = 5 Suppose a complexity function T(n) is eventually nondecreasing and satisfies where b greaterthanorequalto 2 and k greaterthanorequalto 0 are constant integers, and a, c, and d are constants such that a > 0, c > 0, and d greaterthanorequalto 0. T(n) belongs to {theta(n^k) if a b^k. Furthermore, if, in the statement of the recurrence, T(n) = aT(n/b) + cn^k is replaced by T(n) lessthanorequalto aT(n/b) + cn^k or T(n) greaterthanorequalto aT(n/b) + cn^k, then Result B.5 holds with \"big O\" or ohm, respectively, replacing theta.

Solution

a)Comparing (a) with Master theorem,a=2,b=5,c=6,k=3

2< 5³

i.e. a<b³

Hence ,Order is O(n³)

b)

Comparing (b) with Master theorem,a=40,b=3,c=2,k=3

40>3³

i.e.a>b^k

O(n^log3(40))

===================================================