Question

I..Use the mater theorem to determine the time complexity of the following recurrence. Clearly show how you arrived at your solution b) T(n)=2T(n/2)+nlogn b)T(n)=T(n/2) +2n e)

Answer 1

b)
$T(n) = 2T(n/2) + n\log{n}\\ 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=2,\;b=2\;\\ n^{\log_b{a}}=n^{\log_2{2}}=n^{1}=n\\ so,\;this\;comes\;under\;case\;2\\ so,\;time\;complexity\;is\;\Theta(f(n)\log{n})=\Theta(n\log^2{n})\\$

c)

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