در مورد سوال دوم log7 در مبنای ۲ معادل عدد ۲/۸۱ هستش حالا چون ما مقدار دقیق رو می خواییم از [tex]\theta[/tex] استفاده کنیم چون ۲/۸۱>2 لذا [tex]\theta (n^{2.81})[/tex]

---

در مورد سوال اول در این الگوریتم تا حدی از تعداد عملیات ضرب کم می شود و از [tex]n^{3}[/tex] به [tex]n^{2.81}[/tex] کاهش دارد.اما عملیات جمع که در حالت بدون تقسیم و غلبه ۴ تا بود به ۱۸ تا افزایش می یابد یعنی از تعداد ضرب کم و به تعداد جمع اضافه می کنیم اما چون عملیات مدنظر همان ضرب است لذا این الگوریتم کاراتر است .
شما دقت کن هر چه مقدار n بیشتر میشه عملیات جمع هم زیاد میشه . اگه n=2 باشد دقیقا ۷ عمل ضرب و ۱۸ عمل جمع داریم حال شما n=4 باشد چون عملیات جمع به ضرب وابسته هست عملیات جمع افزایش میابد [tex]T(n=4)=7T(2) 18(2)^{2}=7*18 18*4=198[/tex] با هر تعداد افزایش n عملیات جمع بشدت زیاد می شود

برای یادگیری کامل این مطلب میتونید به کتاب راهیان ارشد رجوع کنید

ممنون

اما متوجه نمیشوم که چه عملیاتی [tex]t(n)=7t(\frac{n}{2}) 18(\frac{n}{2})^{2}[/tex] میشود تا استراسن به این فرمول میرسد [tex]6n^{2.81}-6n^{2}[/tex]

ببین دوست من این بر میگرده به حل روابط بازگشتی این تابع بازگشتی [tex]T(n)=7T(n/2) (18/4)n^{2}[/tex] به فرم [tex]T(n)=aT(n/b) Cn^{k}[/tex] می باشد که برای حل آن باید [tex]a[/tex] را با [tex]b^{k}[/tex] مقایسه کنیم اینجا [tex](a=7) >(b^{k}=2^{2}=4)[/tex] چون [tex]a[/tex] بزرگتر است جواب معادله می شود [tex]\theta (n^ {log7})=\theta (n^{2.81})[/tex]

برای یادگیری روابط بازگشتی به کتاب راهیان یا پوران یا مراجع مثل نیپولیتان و clrs رجوع کنید