[go: up one dir, main page]
Scribd
Upload
15 views8 pages

On DAA

The document discusses the Master Theorem, a method for analyzing the time complexity of divide-and-conquer algorithms by solving specific recurrence relations. It outlines the theorem's three cases based on the growth of the function f(n) compared to n^(log_b(a)), and provides examples to illustrate its application. While the Master Theorem is efficient and widely applicable, it has limitations in handling irregular growth patterns and multiple recurrences.

Uploaded by

sb505158
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
15 views8 pages

On DAA

The document discusses the Master Theorem, a method for analyzing the time complexity of divide-and-conquer algorithms by solving specific recurrence relations. It outlines the theorem's three cases based on the growth of the function f(n) compared to n^(log_b(a)), and provides examples to illustrate its application. While the Master Theorem is efficient and widely applicable, it has limitations in handling irregular growth patterns and multiple recurrences.

Uploaded by

sb505158
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/ 8

FUTURE INSTITUE OF TECHNOLOGY

CA2 EVALUATION
REPORT WRITING
MASTER THEOREM METHOD
UNDER THE GUIDANCE OF
PROF.HASNAHANA KHATUN
NAME: BITHIKA SAHA
UNIVERSITY ROLL NO:34230823009
REGISTRATION NO:233420110069
DEPARTMENT: CSE(AI&ML)
PAPER NAME: DESIGN AND ANALYSIS
OF ALGORITHMS
PAPER CODE: PCC-CS404
ABSTRACT:
The master theorem is a fundamental tool used to
analyze the time complexity of divide-and-conquer
algorithms by solving recurrences of the form T(n)=a
T(n/b) +f(n). It provides an efficient way to determine the
asymptotic behavior of such recurrences by comparing
the function f(n) with nlogba. The theorem outlines three
cases based on this comparison: when f(n)grows slower,
at the same rate, or faster than nlogba. Depending on the
case, the time complexity is derived, making the Master
Theorem a widely used technique in algorithm analysis.
However, it is limited to recurrences that fit its specific
form and does not handle all types of divide-and-conquer
recurrences.

INTRODUCTION:
The Master Theorem is a powerful tool used to analyze
the time complexity of recursive algorithms. It provides a
straightforward method for solving recurrences that arise
from divide-and-conquer algorithms. A divide-and-
conquer algorithm divides a problem into subproblems,
solves the subproblems recursively, and combines their
results. The Master Theorem gives us a direct way to
determine the asymptotic behavior (i.e., Big-O) of the
time complexity of such algorithms.

DICUSSION OF BODY:
➢ Recurrence Relations and Their Role:
Divide-and-conquer algorithms often result in
recursive relations that describe the time complexity
of breaking down a problem. The Master Theorem
applies to recurrences of the form
T(n)=a T(n/b) +f(n).
Where:
f(n)=θ (nk (log n)) p
T(n)=a+(n/b) + θ (nk (log n)) p
a>=1, a=no. of problems
b>1, n/b=size of each subproblem.
k=power of n
p=power of log n
➢ The Three Cases of the Master Theorem:
The Master Theorem identifies the asymptotic
behavior of recurrences based on the comparison
between f(n) and nlogba ,where nlogba is the work done
in the recursive calls. The following are the three
cases described in the theorem:

CASE I: If a>bk i.e., logba>k, then T(n)= θ(nlogba)


CASE II: If a=bk that means logba=k
(i) If p>=-1 =>T(n)= θ (nk (log n) p)
(ii) If p=-1 =>T(n)= θ (nk (log log n)
(iii) If p<=-1 => T(n)= θ (nk)
CASE III: If a>bk that means logba<k
(i) If p>=0 => T(n)= θ (nk (log n) p)
(ii) If p<0 => T(n)= θ (nk)
Example:
(a). T(n)=8T(n/2) +n
Where a=8, the number of subproblems.
b=2, the factor by which the problem size is reduced.
k=1, power of n,
p=0, power of log n
Calculate nlogba
logba=log28=3
Since 3>k so it satisfies the first case of master
theorem,
T(n)= θ(nlogba)= θ(n3)
(b). T(n)=4T(n/4) +nlogn
Where a=4, the number of subproblems.
b=4, the factor by which the problem size is reduced.
k=1, power of n,
p=1, power of log n
Calculate nlogba
logba=log44=1
Since 1=k, so it satisfies the second case of master
theorem, also second case of master theorem has 3
subcase since p>=1 so it follows the first subcase
T(n)= θ (nk (log n) p+1) = θ (n log n)2
(c). T(n)=2T(n/2) +n/logn
Where a=2, the number of subproblems.
b=2, the factor by which the problem size is reduced.
k=1, power of n,
p=-1, power of log n
Calculate nlogba
logba=log22=1
Since 1=k, so it satisfies the second case of master
theorem, also second case of master theorem has 3
subcase since p=-1 so it follows the second subcase
T(n)= θ (nk (log log n)) = θ (log log n)
(d). 2T(n/2) +n2logn
Where a=2, the number of subproblems.
b=2, the factor by which the problem size is reduced.
k=2, power of n,
p=1, power of log n
Calculate nlogba
logba=log22=1
Since 1<k, so it satisfies the third case of master
theorem, also third case of master theorem has 2
subcase since p=1 so it follows the first subcase if p>=0
T(n)= θ (nk (log n) p) = θ(n2(logn))

➢ Advantages and disadvantages of master


theorem method:
ADVANTAGES:
• Simplicity: Provides a straightforward and
quick method to solve recurrences for
divide-and-conquer algorithms.
• Efficiency: Saves time by avoiding detailed
expansions or recursive tree analysis.
• Wide Applicability: Suitable for many
common algorithms like merge sort and
quicksort.
DISADVANTAGES:
• Assumptions May Not Hold: Cannot
handle irregular growth patterns in f(n).
• Limited Applicability: Only works for
recurrences of the form T(n)=aT(n/b)
+f(n)T(n) = a T(n/b) + f(n).
• Inability to Handle Multiple
Recurrences: Struggles with algorithms
involving multiple recursive calls.

CONCLUSION:
The Master Theorem is a powerful and efficient tool for
analyzing the time complexity of divide-and-conquer
algorithms. It provides a quick way to solve recurrences
of the form T(n)=a T(n/b) +f(n). offering clear insights into
the asymptotic behavior of such algorithms. However, its
applicability is limited to specific types of recurrences,
and it cannot handle more complex or irregular
recursions. Despite its limitations, it remains an essential
technique for many common algorithmic analyses.

REFERENCES:
[1] https://www.geeksforgeeks.org/advanced-master-
theorem-for-divide-and-conquer-recurrences/ [An online
resource for the information about Master Theorem
Method]
[2]. https://www.geeksforgeeks.org/advanced-master-
theorem-for-divide-and-conquer-recurrences/ [An online
resource for the examples of Master Theorem Method].

You might also like