این سوال هم با جایگذاری حل میشه فقط وقتی به بعد ۳ رسیدیم عدد 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 هم به سمت صفر میره.