In the analysis of algorithms, the master theorem provides a cookbook solution in asymptotic terms (using Big O notation) for recurrence relations of types that occur in the analysis of many divide and conquer algorithms. It was popularized by the canonical algorithms textbook Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, in which it is both introduced and proved. Nevertheless, not all recurrence relations can be solved with the use of the master theorem; its generalizations include the Akra–Bazzi method.
Read more about Master Theorem: Introduction, Generic Form, Inadmissible Equations
Famous quotes containing the words master and/or theorem:
“The beasts, the fishes, and the winged fowls
Are their males’ subjects and at their controls:
Man, more divine, the master of all these,
Lord of the wide world and wild watery seas,
Indued with intellectual sense and souls,
Of more pre-eminence than fish and fowls,
Are masters to their females, and their lords:
Then let your will attend on their accords.”
—William Shakespeare (1564–1616)
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)