in Algorithms edited by
1,828 views
1 vote
1 vote
On which of the following recurrence relation Masters theorem can not be applied ?

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

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

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

D. T(n) = 7(T(n/4) + n2.
in Algorithms edited by
by
1.8k views

2 Answers

1 vote
1 vote
Best answer

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

4 Comments

Please see the below details form CLRS, Ch.4

0
0

@Manu you are correct. Option A is the answer here but still we can apply extended Master theorem on it as shown here which gives $T(n) = \Theta\left(n \log^2 n\right).$

https://gateoverflow.in/10619/recurrence

2
2
@Arjun. Thank you. That is a good information. :)
1
1
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

by

3 Comments

You are right..
0
0
No, you are wrong. You can see the definitions in Cormen and particularly the $\epsilon$ part.
0
0
Okay sir,

So u suggest  option A is the answer and the reason is as explained in above answer, is nt it??

[Thank you for bringing these in depth details on light.. I bet many people had not known this. Thanks again]
0
0