The Gateway to Computer Science Excellence
0 votes
98 views
How to check if a given recurrence relation is in a format that is valid to apply Master’s Theorem? Also, how to distinguish between Master’s Theorem and extended Master’s Theorem?
in Algorithms by (235 points) | 98 views
+2

The equation should be in the form of  $aT(\frac{n}{b}) + O(n^{k} log^{p}n)$ where a$\geq$1 and b>1 and k$\geq$0 and p is a real number.

If you can convert the given recurrence relation in this form then you can apply master theorem.

This version is used for divide and conquer type of problems like mergesort, quicksort etc

The extended master theorem is used for  subtract and conquer, that is when the bigger problem is like sum of smaller subproblems.

it is of the form $aT(n-b) + O(n^{k})$

https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)#Inadmissible_equations

The above are some cases where you can't apply master theorem.

0

@Satbir Thanks for your reply. The link clarified almost all of my doubts. I am still confused regarding the violation by

$T(n) = 2T(\frac{n}{2}) + \frac{n}{logn}$

Could you please clarify this? Thanks.

0
$T(n)= 2T\left ( \frac{n}{2} \right )+\frac{n}{log n}$

$\implies T(n)= 2T\left ( \frac{n}{2} \right )+n(logn)^{-1}$

$\implies T(n)= 2T\left ( \frac{n}{2} \right )-n(logn)$

here f(n) is not positive so we can't apply master's theorem.
+1

@Satbir $ \log(n^{-1}) = -\log n \neq (\log n)^{-1} $

0
then it will can apply master theorem.

a=2,b=2,k=1,p=-1

$a=b^{k}$ and p=-1

so $T(n) = \theta(n\ loglog\ n)$
0

@smsubham

Are you sure about that ?

https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)#Inadmissible_equations

read the about the 2nd case....I have used extended version of master theorem.

+1
I was talking about master theorem only. The extended master theorem can be applied.

1 Answer

+1 vote
Best answer

The equation should be in the form of  $aT(\frac{n}{b}) + O(n^{k} log^{p}n)$ where $a\geq1$ and $b>1$ and $k\geq0$ and $p$ is a real number.

If you can convert the given recurrence relation in this form then you can apply master theorem.

This version is used for divide and conquer type of problems like mergesort, quicksort etc

Another version pf master theorem is used for  subtract and conquer, that is when the bigger problem is like sum of smaller subproblems.

it is of the form $aT(n-b) + O(n^{k})$

https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)#Inadmissible_equations

The above are some cases where you can't apply master theorem.

 

by Boss (21.6k points)
edited by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,644 questions
56,512 answers
195,559 comments
101,073 users