اول تغییر متغیر زیر رو در نظر می گیریم:
n=2k⇒k=lgn
حالا شکل معادله رو بعد از اعمال تغییر متغیر می نویسیم:
T(2k)=T(2k−1)2kk
حالا با در نظر گرفتن
S(k)=T(2k) داریم:
S(k)=S(k−1)2kk
معادله بالا یک معادله بازگشتی نا همگن با ضرایب ثابت هستش که معادله مشخصه اون به صورت زیر هستش:
(k−2)2=0
معادله بالا ریشه مضاعف داره و اگر ریشهها رو در جواب عمومی معادلات بازگشتی قرار بدیم داریم:
S(k)=C12kC2k2k
حالا با تغییر متغیر معکوس داریم:
T(n)=C1nC2nlgn
پس T از مرتبه تتای nlgn هستش
پ.ن: جواب رو با توجه به اون چیزهایی که از این بحث یادم می اومد نوشتم و ممکنه صد در صد درست نباشه