This is a written assignment and should be handed in person at the beginning of

Question

This is a written assignment and should be handed in person at the beginning of class on the submission date. 1. For this problem, you need to provide reasoning for your answer. Just providing an order will not get you any points. (30 points) Rank the following functions by order of growth; that is, find an arrangement 81,82, ,830 of the functions satisfying gi (82), g2 --(gs), , 829 (830). Partition your list into equivalence classes such that functions f(n) and g(n) are in the same class if and only if f(n)--(g(n)) lg0lgn)2)gnn2 n! lgn)! (2) gn g(n!)" n/gn In Inn g*n n 2g Inn 1 g n g n g n lg' lg n) 2v2ign n 2" n lg 22 1 n lgn 22 2n+1

Explanation / Answer

Answer 2:

a. T(n) = 2T(n/2) + n^3

Using Master's theorm we have

a = 2 , b = 2 , c = 3 , f(n) = n^3

Now , log b base a = log 2 base 2 = 1

Here c > log b base a , therefore Case 1 applies here T(n) = theta(n^logb base a) = theta(n)

Therefore T(n) = theta(n)

b. T(n) = 9T(n/10) + n

Using Masters theorem we have

a = 9 , b = 10 , c = 1 , f(n) = n

Now log b base a = log10 base 9 = 1

Here c = log a base b , therefore Case 2 applies here

T(n) = theta(n^clog a base b) = theta(n^clogn) = theta(n^1logn) = theta(nlogn)

c . T(n) = 16T(n/4) + n^2

Using Masters theorem we have

Here a = 16 , b = 4 , c = 2 , f(n) = n^2

Now log a base b = log 16 base 4 = 2

Here c = log a base b , therefore case 2 applies

T(n) = theta(n^clogn) = theta(n^2logn)

d) T(n) = 7T(n/3) + n^2

Using Master's theorem we have

a = 7 , b = 3 , c = 2 , f(n) = n^2

Now logb base a = log 7 base 3 is almost 1

Here c> loga base b , therefore case 1 applies

T(n) = theta(n^loga base b) = theta(n)

Now see Masters theorm Rules :

Case 1 : If log b base > c , then T(n) = theta(n^log b base a)

Case 2 : If log b base a = c , then T(n) = theta(n^clogn)

Case 3 : if log b base a < c , then T(n) = theta(f(n)

DEAR PLEASE DO RATE IT IF HELPS ELSE LET ME KNOW YOUR DOUBT.

KINDLY POST SEPARATELY AS WE ARE RESTRICTED TO ANSWER MORE THAN ONE QUESTIONS FROM MULTIPLE POSTED QUESTIONS. FURTHERMORE , WE ARE ALLOWED TO ANSWER ONLY FOUR SUBPARTS OF THE QESTION.

THANK YOU!!!

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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