edited by
1,900 views

2 Answers

Best answer
1 votes
1 votes

For master theorem, recurrence should be of the form $T(n)=aT(n/b)+f(n)$, where $a\geq 1$ and $b> 1.$. Intuitively, the 3 cases of the theorem are: 

Case(1): $n^{\log_b(a)}$ should be polynomially larger than $f(n)$

Case(2): $n^{\log_b(a)}$ should be equal to $f(n)$

Case(3): $n^{\log_b(a)}$ should be polynomially smaller than $f(n)$

So, in option(A): $n^{\log_b(a)}=n$ and $f(n)=n\log n,$, which seems to be case (3). But, here $f(n)/n^{\log_ba})=\log n,$ which is not polynomial larger. So Cannot apply Master theorem. [Cormen, Page 96-97]. But we can use Extended Master theorem here and get $T(n) = \Theta\left(n \log^2 n \right)$ as shown here

Option (b) is case (2), so $T(n)=\Theta(n)$

Option(c) is case(1), so $T(n)=\Theta(n^3)$

Option(d) is case(3), so $T(n)=\Theta(n^2)$. Case 3 also requires that $af(n/b) \leq cf(n)$ for some $c < 1$ and all sufficiently large $n$. Here, we get $7 (n/4)^2 \leq c n^2$ is true for $c \geq 7/16$ and all $n\geq 1.$ 

The Answer is Option A

edited by
2 votes
2 votes

Masters theorem can be used to solve relations of the form T(n) = a T(n/b) + f(n) where a≥1 and b>1

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

A. T(n)= 2T(n/2) + n (log n).

a=2 > =1 and b=2 >1 Conditions satisfied.

T(n) =Θ(nlogn)

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

B. T(n) = T(n/2) + 1.

a=1 > =1 and b=2 >1 Conditions satisfied.

T(n) =Θ(logn)

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

C. T(n) = 8T(n/2) + (log n).

a=8> =1 and b=2 >1 Conditions satisfied.

T(n) =Θ(n 3)

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

D. T(n) = 7(T(n/4) + n2.

a=7> =1 and b=4 >1 Conditions satisfied.

T(n) =Θ(n 2)

 

We can apply Masters theorem in all given options.

Corerct me If I am wrong

Related questions

0 votes
0 votes
1 answer
1
rajan asked Dec 9, 2016
381 views
how to solve these two using matser thorem.1. t(n)=2t(√n)+n2. t(n)=4t(√n)+(logn)^2
0 votes
0 votes
1 answer
2
0 votes
0 votes
2 answers
3
0 votes
0 votes
0 answers
4