Master Method: Difference between revisions
Jump to navigation
Jump to search
[Next in Algorithms] [Next in Algorithm Complexity]
No edit summary |
|||
| Line 1: | Line 1: | ||
=Internal= | =Internal= | ||
=Overview= | =Overview= | ||
The <span id='Master_Method'></span>'''master method''' is a method of analyzing running time of recursive algorithms by using the "master theorem". The master theorem applies to algorithms whose running times can be expressed as a [[#Recurrence_Equation|recurrence equation]]. A generic form of a recurrence equation is: | |||
T(n) = a⋅T(n/b) + f(n) | |||
where a ≥ 1, b > 1 and f(n) is a function that approximates the non-recursive cost. Note that the above expression does include a boundary condition for n = 1. The reasons is that T(1) does not significantly change the solution to the recurrence, it may change it with a constant factor, but the order of growth will stay unchanged. | |||
<font color=darkgray>TODO [[CLRS]] page 93.</font> | |||
<font color=darkkhaki>TODO integrate after class:</font> | |||
<font color=darkkhaki>Integrate class https://www.coursera.org/learn/algorithms-divide-conquer/lecture/HkcdO/formal-statement</font> | <font color=darkkhaki>Integrate class https://www.coursera.org/learn/algorithms-divide-conquer/lecture/HkcdO/formal-statement</font> | ||
<center>[[[Algorithms#Recursive_Algorithms_Complexity_-_Master_Method|Next in Algorithms]]] [[[Algorithm_Complexity#The_Master_Method_.28Master_Theorem.29|Next in Algorithm Complexity]]]</center> | <center>[[[Algorithms#Recursive_Algorithms_Complexity_-_Master_Method|Next in Algorithms]]] [[[Algorithm_Complexity#The_Master_Method_.28Master_Theorem.29|Next in Algorithm Complexity]]]</center> | ||
Revision as of 17:24, 20 September 2021
Internal
Overview
The master method is a method of analyzing running time of recursive algorithms by using the "master theorem". The master theorem applies to algorithms whose running times can be expressed as a recurrence equation. A generic form of a recurrence equation is:
T(n) = a⋅T(n/b) + f(n)
where a ≥ 1, b > 1 and f(n) is a function that approximates the non-recursive cost. Note that the above expression does include a boundary condition for n = 1. The reasons is that T(1) does not significantly change the solution to the recurrence, it may change it with a constant factor, but the order of growth will stay unchanged.
TODO CLRS page 93.
TODO integrate after class:
Integrate class https://www.coursera.org/learn/algorithms-divide-conquer/lecture/HkcdO/formal-statement