Recurrence Assuming in each case that T(n) is eventually nondecreasing, use Theo

Question

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.

Explanation / Answer

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

2< 53

i.e. a<b3

Hence ,Order is O(n3)

b)

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

40>33

i.e.a>bk

O(nlog3(40))

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

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.