マスター定理

概要

• 分割統治法の計算量を見積もる定理である
• 計算時間T(n)があるときに、部分問題O(n)が繰り出せるときに以下のように一般化できる

具体例

• binery search
  • T(n) = T(n/2) + O(1) = O(log n)
• merge sort
  • T(n) = 2T(n/2) + O(n) = O(n log n)

参考

• Master theorem (analysis of algorithms)