Question

Suppose that we have two algorithms A1 and A2 for solving the same problem. Let T1(n) be the worst-case time complexity of A1 and T2(n) be the worst-case time complexity of A2. We know that:

T(1)=1

T1(n)=15*T1(n/2)+n^2, n>1

T2(1)=1

T2(n)=80*T2(n/3)+20n^3,n>1

a. Use the master method to decide T1(n)

b. Use the master method to decide T2(n)

c. Which algorithms is more efficient? Why?

Answer 1

a)
$T(n) = 15T(n/2)+n^2\\ This\; is \;in \;the \;form\;of \;T(n) = aT(\frac{n}{b}) + f(n)\\ so,\;we\;can\;use\;master's\;theorem.\\ compare\;n^{\log_b{a}}\;with\;f(n)\\ a=15,\;b=2\;\\ n^{\log_b{a}}=n^{\log_2{15}}=n^{3.91}\\ n^{\log_b{a}}=n^{\log_2{15}}=n^{3.91}\;>\;f(n)=n^2\\ so,\;this\;comes\;under\;case\;1\\ so,\;time\;complexity\;is\;\Theta(f(n))=\Theta(n^{3.91})\\$

b)
$T(n) = 80T(n/3)+n^3\\ This\; is \;in \;the \;form\;of \;T(n) = aT(\frac{n}{b}) + f(n)\\ so,\;we\;can\;use\;master's\;theorem.\\ compare\;n^{\log_b{a}}\;with\;f(n)\\ a=80,\;b=3\;\\ n^{\log_b{a}}=n^{\log_3{80}}=n^{3.99}\\ n^{\log_b{a}}=n^{\log_3{80}}=n^{3.99}\;>\;f(n)=n^3\\ so,\;this\;comes\;under\;case\;1\\ so,\;time\;complexity\;is\;\Theta(f(n))=\Theta(n^{3.99})\\$


c)
T1 is more efficient.
because n^3.91 is smaller than n^3.99