分割統治法の計算量
計算量
$ \begin{cases}T(1)=O(1) & (n=1) \\ T(n)=2 T\left(\frac{n}{2}\right)+O(n) & (\text { other })\end{cases}
一般に
以下のような漸化式は
$ T(1)=O(1)
$ T(n)=aT(\frac{n}{b})+O(n)
$ n\gt 1のとき
以下のようになる
$ T(n)= \begin{cases}O(n) & (a<b) \\ O(n \log n) & (a=b) \\ O\left(n^{\log _{b} a}\right) & (a>b)\end{cases}
この漸化式の解法