سلام.
چون توی بعضی از روابط بازگشتی گاهی رادیکال داریم محاسبه ش سخت هست و با روش های معمولی نمیتونیم احتمالا حلش کنیم. باید یه کاری کنیم که از شر رادیکال خلاص بشیم.
این جا برای این که رادیکال رو از بین ببریم شاید پیشنهاد بشه که رادیکال رو به صورت توان [tex]\frac{1}{2}[/tex] بنویسیم. اما خب فرقی نداره و بعدش نمیشه هیچ کاری کرد. این جا ها که رادیکال داریم میشه ۲ به توان m گرفت n رو. اگه رادیکال تودرتو بود و اینا فرق داشت قضیه.
[tex]T(n)=3T(\sqrt[3]{n})+\log n[/tex]
حالا تغییر متغیر برای خلاص شدن از رادیکال: [tex]n=2^m\: \longrightarrow\: \log n=m[/tex]
[tex]T(2^m)=3T(\sqrt[3]{2^m})+\log2^m=3T(2^{\frac{m}{3}})+m[/tex]تغییر متغیر دوم برای تبدیل به رابطه ی بازگشتی غیر توانی : [tex]T(2^m)=S(m)[/tex]
[tex]S(m)=3S(\frac{m}{3})+m[/tex] که از مرتبه ی mlogm هست و چون [tex]\log n=m[/tex] پس میشه از مرتبه ی [tex]\log n\times\log\log n[/tex]