Master theorem (analysis of algorithms)

In the <a href="/facts/Analysis_of_algorithms/pStoBgBn">analysis of algorithms</a>, the master theorem for divide-and-conquer recurrences provides an <a href="/facts/Asymptotic_analysis/kt87qLpu">asymptotic analysis</a> for many <a href="/facts/Recurrence_relation/JolXC71M">recurrence relations</a> that occur in the <a href="/facts/Analysis_of_algorithms/pStoBgBn">analysis</a> of <a href="/facts/Divide_and_conquer_algorithm/pC1X7Ws7">divide-and-conquer algorithms</a>. The approach was first presented by <a href="/facts/Jon_Bentley_(computer_scientist)/WEK7bgSs">Jon Bentley</a>, <a href="/facts/Dorothea_Blostein/8PBoDtgm">Dorothea Blostein</a> (née Haken), and <a href="/facts/James_B._Saxe/Xgf5vrzu">James B. Saxe</a> in 1980, where it was described as a "unifying method" for solving such recurrences. The name "master theorem" was popularized by the widely used algorithms textbook <a href="/facts/Introduction_to_Algorithms/o9n7KDsg">Introduction to Algorithms</a> by <a href="/facts/Thomas_H._Cormen/qJ2Ys15T">Cormen</a>, <a href="/facts/Charles_E._Leiserson/6Uf19apB">Leiserson</a>, <a href="/facts/Ron_Rivest/nQsIcAKa">Rivest</a>, and <a href="/facts/Clifford_Stein/5ajkVbCm">Stein</a>.
Not all recurrence relations can be solved by this theorem; its generalizations include the <a href="/facts/Akra%E2%80%93Bazzi_method/sCFyt4dE">Akra–Bazzi method</a>.

Master theorem (analysis of algorithms) open-in-new

Master theorem (analysis of algorithms)