Master Method: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 17: Line 17:


<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>
==Analyzing Divide-and-Conquer Algorithms==
<font color=darkkhaki>TODO integrate after class:</font>
For [[Algorithms#Divide_and_Conquer|divide-and-conquer recursive problems]], where solving the problem involves dividing the problem into ''a'' subproblems of size ''n/b'' of the original', applying the algorithm recursively ''a'' times on ''n/b''-size problems and then combining the result, the run time can be expressed by the generic recurrence presented below. If the problem size is small enough (n ≤ c) the straightforward solution takes constant time, which is expressed as a constant function [[#Constant_Function|Θ(1)]].
        | Θ(1)                    if n ≤ c
T(n) = |
        | aT(n/b) + D(n) + C(n)    otherwise
where the D(n) is the cost of dividing the n-size problem into a subproblems, and the C(n) is the cost of combining the results.


<center>&#91;[[Algorithms#Recursive_Algorithms_Complexity_-_Master_Method|Next in Algorithms]]] &#91;[[Algorithm_Complexity#The_Master_Method_.28Master_Theorem.29|Next in Algorithm Complexity]]]</center>
<center>&#91;[[Algorithms#Recursive_Algorithms_Complexity_-_Master_Method|Next in Algorithms]]] &#91;[[Algorithm_Complexity#The_Master_Method_.28Master_Theorem.29|Next in Algorithm Complexity]]]</center>

Revision as of 17:25, 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


Analyzing Divide-and-Conquer Algorithms

TODO integrate after class:

For divide-and-conquer recursive problems, where solving the problem involves dividing the problem into a subproblems of size n/b of the original', applying the algorithm recursively a times on n/b-size problems and then combining the result, the run time can be expressed by the generic recurrence presented below. If the problem size is small enough (n ≤ c) the straightforward solution takes constant time, which is expressed as a constant function Θ(1).

       | Θ(1)                     if n ≤ c
T(n) = |
       | aT(n/b) + D(n) + C(n)    otherwise

where the D(n) is the cost of dividing the n-size problem into a subproblems, and the C(n) is the cost of combining the results.






[Next in Algorithms] [Next in Algorithm Complexity]