基本的な分割統治は,最悪実行時間をT(n)T(n)T(n)とすると, T(n)={O(1)(n=1)2T(n2)+O(n)(otherwise) T(n) = \begin{cases} O(1) &(n =1)\\ 2T(\frac{n}{2}) + O(n)&(otherwise) \end{cases} T(n)={O(1)2T(2n)+O(n)(n=1)(otherwise) という形で書き表すことができ,T(n)=O(nlogn)T(n) = O(n \log n)T(n)=O(nlogn)であることが知られています このことは,図で書き表すことによりすぐにわかります.つまり,12\frac{1}{2}21になっていくのでn=1n=1n=1にlogn\log nlogn回の再帰でたどり着き,各深さで合計O(n)O(n)O(n)しかかからないのでO(nl