صورت سوال را برای خوانایی بیشتر مجددا قرار دادم.
[tex]T(2^k)=3T(2^{k-1}) 2^{\frac{3k}{2}}[/tex]

[tex]T(n)=T(\frac{n}{9}) T(\frac{8n}{9}) θ(n)[/tex]

___________________________________________________________________


سوال دوم خیلی ساده است :
[tex]T(n)=T(\frac{n}{9}) T(\frac{8n}{9}) θ(n)[/tex]

باید درخت بازگشتی آن را رسم کنید و پاسخ آن می شود :
[tex]\theta(nlogn)[/tex]


------------------------------------------------------------------------------
برای حل سوال اول باید از تغییر متغیر زیر استفاده کنید :
[tex]m\: =\: 2k[/tex]

رابطه به این شکل می شود :
[tex]T(m)=3T(\frac{m}{2}) m^{\frac{3}{2}}[/tex]

این رابطه با استفاده از قضیه Master قابل حل است که می شود :
[tex]T(m)=\theta(m^{\frac{3}{2}})[/tex]

حالا m را جا گذاری نمایید :
[tex]T(2^k)=\theta(2^{\frac{3k}{2}})[/tex]