سوال:$T\left ( n \right )= 2T \left ( \frac{n}{2} \right )\dotplus n\log n$

تعمیم قضیه اصلی: صفحه ۷۹ کتاب طراحی الگوریتم مقسمی

$T\left ( n \right )= aT\left ( n/b \right ) c f\left ( n \right )$

اگر $n^{log_{b}^{a}}> O\left ( f\left ( n \right ) \right )$

$T\left ( n \right )= O\left (n^{log _{b}^{a}} \right )$

اگر $n^{log_{b}^{a}}< O\left ( f\left ( n \right ) \right )$

$T\left ( n \right )= O\left ( f\left ( n \right ) \right )$

اگر $a= b$

$T\left ( n \right )= \log n\ast O\left ( f\left ( n \right ) \right )$

شرط سوم برقرار میشه و جواب $T\left ( n \right )= O\left ( n\cdot log^{2}n \right )$