سوال:[tex]T\left ( n \right )= 2T \left ( \frac{n}{2} \right )\dotplus n\log n[/tex]

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

[tex]T\left ( n \right )= aT\left ( n/b \right ) c f\left ( n \right )[/tex]

اگر [tex] n^{log_{b}^{a}}> O\left ( f\left ( n \right ) \right )[/tex]

[tex]T\left ( n \right )= O\left (n^{log _{b}^{a}} \right )[/tex]

اگر [tex]n^{log_{b}^{a}}< O\left ( f\left ( n \right ) \right )[/tex]

[tex]T\left ( n \right )= O\left ( f\left ( n \right ) \right )[/tex]

اگر [tex]a= b[/tex]

[tex]T\left ( n \right )= \log n\ast O\left ( f\left ( n \right ) \right )[/tex]

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