24. Assuming in each case that T (n) is eventually nondecreasing, use Theorem B.

Question

24. Assuming in each case that T (n) is eventually nondecreasing, use Theorem B.5 to determine the order of the following recurrence equations (a) T(n) = 2T()-6n3 for n > 1, n a power of 5 (b) T(n)-40T2n3for n1, n a power of 3 (c) nT (n) = 167, G) +7n4 for n > 1, n a power of 2 T(1) = 6 T (1) 5 T (1) = 1 25. Assuming in each case that T (n) is eventually nondecreasing, use Theorem B.6 to determine the order of the following recurrence equations (a) T(n) = 14ng)+6n for n > 25, n a power of 5 T (25) = 60 (b) T (n) = 41, ( ) +2n2 for n > 16, n a power of 4 T (16) 50

Explanation / Answer

Explanation: We can use Masters theoremk to solve our problem,

If T(n) = aT(n/b) + f(n) , then it can be solved using Masters method and we need to see if it falls into Case 1, 2 or 3

1) T(n) = 2T(n/5) + 6n3
Comparing it with aT(n/b) + f(n) we get
a = 2 , b = 5 and f(n) = 6n3 = O(n3)
=> nlogb a = nlog5 2 = n0.43
We can see that f(n) >= g(n) i.e n3 > n0.43

It falls into Case 3 of masters method i.e T(n) = O(n3)

2) T(n) = 40T(n/3) + 2n3
Comparing it with aT(n/b) + f(n) we get
a = 40 , b = 3 and f(n) = 2n3 = O(n3)
=> nlogb a = nlog3 40 = n3.35
We can see that c*g(n) >= f(n) i.e n3.35 > n3

It falls into Case 1 of masters method i.e T(n) = O(n3.35 )

3) T(n) = 16T(n/4) + 7n4
Comparing it with aT(n/b) + f(n) we get
a = 16 , b = 4 and f(n) = 7n4 = O(n4)
=> nlogb a = nlog216 = n4
We can see that g(n) = f(n) i.e n4 = n 4

It falls into Case 2 of masters method i.e T(n) = O(n4 log n )

25)

T(n) = 14T(n/5) + 6n
Comparing it with aT(n/b) + f(n) we get
a = 14 , b = 5 and f(n) = 6n = O(n)
=> nlogb a = nlog514 = n1.63
We can see that c*g(n) >= f(n) i.e n1.63 > n

It falls into Case 1 of masters method i.e T(n) = O(n1.63 )

T(n) = 4T(n/4) + 2n2
Comparing it with aT(n/b) + f(n) we get
a = 4 , b = 4 and f(n) = 2n2 = O(n2)
=> nlogb a = nlog4 4 = n1
We can see that f(n) >= g(n) i.e n2 > n

It falls into Case 1 of masters method i.e T(n) = O(n2 )

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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