اگر بتوانیم ماتریس های ۳×۳ را با k ضرب اسکالر در هم ضرب کنیم بزرگترین k چند است به طوری که بتوانیم ماتریس های n*n را در زمان [tex]O(n^{lg7})[/tex]
در هم ضرب کنیم؟زمان اجرای این الگوریتم چگونه است؟(سوال Clrs هست)
این سوال هم با جایگذاری حل میشه فقط وقتی به بعد ۳ رسیدیم عدد K رو جایگذاری می کنیم:
[tex]T\left( n \right )=7 T\left (\frac{n}{2} \right )= ....= 7^{i}T\left( \frac{n}{2^{i}} \right )[/tex]
با توجه به اینکه تا بعد ۳ بیشتر نمشکنیم پس i برابر است با:
[tex]T\left (3 \right )=k \Rightarrow \frac{n}{2^{i}}=3\Rightarrow i= \lg \frac{n}{3}\Rightarrow T\left( n \right )= 7^{\lg \frac{n}{3}}\times k[/tex]
خوب حالا مقدار بالا باید محدود بشه به:
[tex]T\left( n \right )= 7^{\lg \frac{n}{3}}\times k = O\left( n^{\lg 7} \right )\: \: \Rightarrow 7^{\lg \frac{n}{3}}\times k\leq \, c\times n^{\lg 7}\, \Rightarrow k\leq c\, \frac{n^{\lg 7}}{\lg \frac{n}{3}}[/tex]
که اگر n به سمت بی نهایت بره k هم به سمت صفر میره.