International Research Journal of Engineering and Technology (IRJET)
e-ISSN: 2395-0056
Volume: 10 Issue: 04 | Apr 2023
p-ISSN: 2395-0072
www.irjet.net
Master’s theorem Derivative Analysis Renvil Dsa1, Savio Rodricks2, Manobala Subramaniam3 1Renvil Dsa Fr. Conceicao Rodrigues College of Engineering, Mumbai, India
2Savio Rodricks Fr. Conceicao Rodrigues College of Engineering, Mumbai, India
3Manobala Subramaniam Fr. Conceicao Rodrigues College of Engineering, Mumbai, India
---------------------------------------------------------------------***---------------------------------------------------------------------
Abstract: This research paper explores the potential use
The paper illustrates the application of the Master's Theorem with several examples, including the merge sort algorithm, the binary search algorithm, and the Towers of Hanoi problem. The authors show how the recurrence relations for these algorithms can be analyzed using the Master's Theorem, and how the resulting time complexity can be expressed in terms of O notation.
of the Master's Theorem in estimating the derivatives of iterative functions, which represents a novel application of this mathematical tool. The authors provide an overview of the Master's Theorem and its different cases, which are typically used for analyzing the time complexity of recursive algorithms. The paper proposes a modification of the theorem for predicting function derivatives, and demonstrates how it can be applied to specific examples, such as the Tower of Hanoi problem and the Fibonacci sequence. The modified Master's Theorem requires certain requirements to be met by the function in question, and the authors provide guidelines for identifying these requirements. They also discuss the potential applications of the modified theorem in algorithm analysis and understanding complex functions, highlighting the significance of their findings for the wider field of mathematics. Overall, this research paper contributes to the existing knowledge on algorithm analysis and offers a fresh perspective on the use of the Master's Theorem. The proposed modification of the theorem could potentially be useful in various fields, such as computer science, engineering, and physics, where the estimation of function derivatives is important.
Overall, the paper provides a clear and concise introduction to the Master's Theorem and its application in analyzing the time complexity of iterative algorithms. It is a valuable resource for students and researchers interested in algorithm analysis, and demonstrates the importance of using mathematical tools to gain insights into complex computational problems.
Master Theorem Cases and Their Applications:
Keywords: Master's Theorem, derivatives, iterative functions, recursive algorithms, complexity analysis, subproblems, the Tower of Hanoi, the Fibonacci sequence, and algorithm analysis.
Case
Condition
Application
Case 1
If for some ε > 0, then .
Applies to divide-andconquer algorithms with roughly equal subproblems
Case 2
If
Applies to algorithms with subproblems that are either much smaller or much larger than the input
,
1. INTRODUCTION
then
The Master's Theorem is generally applicable to recurrence relations of the form T(n) = aT(n/b) + f(n), where T(n) is the execution time of the algorithm on a problem of size n, a is the number of subproblems generated by the algorithm at each level, each of size n/b, and f(n) is the time spent on processing the problem at the current level. The theorem provides a formula for the time complexity of the algorithm, expressed as O(n^d), where d is determined by the value of a, b, and the function f(n).
.
Case 3
The paper explains the three cases of the Master's Theorem, each corresponding to a different value of d.
© 2023, IRJET
|
Impact Factor value: 8.226
|
If for some ε > 0, and if a * f(n/b) ≤ c * f(n) for some constant c < 1 and all sufficiently large n, then
ISO 9001:2008 Certified Journal
Applies to algorithms that have a variable number of subproblems depending on the input size.
|
Page 1646