Master Method: Difference between revisions
(→TODO) |
|||
Line 34: | Line 34: | ||
=TODO= | |||
<font color=darkkhaki> | |||
* intuition | |||
* definition | |||
* proof | |||
* Emphasize that is theta, not O | |||
</font> | |||
Revision as of 17:31, 21 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.
TODO
- intuition
- definition
- proof
- Emphasize that is theta, not O