Scribd
Upload
4 views6 pages

s8

The document introduces the Master Method for solving recurrences of the form T(n) = aT(n/b) + f(n), detailing three cases for determining the complexity based on the relationship between f(n) and n^(log_b(a)). It provides examples of solving specific recurrences, illustrating how to apply the method to find the complexities T(n) = Θ(n^2), T(n) = Θ(n^(2.8)), and T(n) = Θ(n^2 log n). The document emphasizes the conditions under which each case applies.

Uploaded by

Sanjay Baskar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views6 pages

s8

The document introduces the Master Method for solving recurrences of the form T(n) = aT(n/b) + f(n), detailing three cases for determining the complexity based on the relationship between f(n) and n^(log_b(a)). It provides examples of solving specific recurrences, illustrating how to apply the method to find the complexities T(n) = Θ(n^2), T(n) = Θ(n^(2.8)), and T(n) = Θ(n^2 log n). The document emphasizes the conditions under which each case applies.

Uploaded by

Sanjay Baskar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

UNIT I

INTRODUCTION TO ALGORITM
DESIGN
Master’s theorem method
⚫ Master Method is a direct way to get the solution. The master method
works only for following type of recurrences or for recurrences that
can be transformed to following type.

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1 and f(n) is an asymptotically
positive function.

⚫ There are following three cases:

1. If f(n) < O(nlogba), then T (n) = ϴ (nlogba).

2. If f(n) = ϴ (nlogba) , then T (n) = ϴ (nlogbalogn).

3. If f(n) > Ω (nlogba), and f(n) satisfies the regularity condition, then
T (n) = ϴ (f(n)).
Solve the problems
⚫ T(n) = 3T(n/2) + n2
⚫ T(n) = 7T(n/2) + n2
⚫ T(n) = 4T(n/2) + n2
⚫ T(n) = 3T(n/4) + n lg n
T(n) = 3T(n/2) + n2
T(n) = aT(n/b) + f(n) where a >= 1 and b > 1
a=3 b=2 f(n) = n2
1. If f(n) < O(nlogba), then T (n) = ϴ (nlogba).
2. If f(n) = ϴ (nlogba) , then T (n) = ϴ (nlogbalogn).
3. If f(n) > Ω (nlogba), and f(n) satisfies the regularity condition,
then T (n) = ϴ (f(n)).
Step 1: Calculate nlogba = nlog23 = n1.58
Step 2: Compare with f(n)
Since f(n) > nlogba
i.e. n2 > n1.58
Step 3: Case 3 is satisfied hence complexity is given as
T(n) = Θ(f(n)) = Θ (n2)
2
T(n) = 7T(n/2) + n
T(n) = aT(n/b) + f(n) where a >= 1 and b > 1
a=7 b=2 f(n) = n2
1. If f(n) < O(nlogba), then T (n) = ϴ (nlogba).
2. If f(n) = ϴ (nlogba) , then T (n) = ϴ (nlogbalogn).
3. If f(n) > Ω (nlogba), and f(n) satisfies the regularity
condition, then T (n) = ϴ (f(n)).
Step 1: Calculate nlogba = nlog27= n2.80
Step 2: Compare with f(n)
since f(n) < nlogba
Step 3: Case 1 is satisfied hence complexity is given as
T(n) = Θ (nlogba) = Θ (n2.8)
2
T(n) = 4T(n/2) + n
T(n) = aT(n/b) + f(n) where a >= 1 and b > 1
a=4 b=2 f(n) = n2

1. If f(n) < O(nlogba), then T (n) = ϴ (nlogba).

2. If f(n) = ϴ (nlogba) , then T (n) = ϴ (nlogbalogn).

3. If f(n) > Ω (nlogba), and f(n) satisfies the regularity condition, then T
(n) = ϴ (f(n)).

Step 1: Calculate nlogba = nlog24= n2

Step 2: Compare with f(n) // Since f(n) = nlogba * log0n

Step 3: Case 2 is satisfied hence complexity is given as

T(n) = Θ (f(n)logn) = Θ (n2logn)

You might also like