در مورد سوال اول همان طور که ذکر کرده عبارت [tex]S(n)=2T(n/3) \theta (n^{\sqrt{lgn}})[/tex] را به جای [tex]T(n)[/tex] قرار داده

چون [tex]T(n)\leq S(n)[/tex] یعنی به جای عبارت [tex]T(n/6)[/tex] چون [tex]T(n/6)\leq T(n/3)[/tex] عبارت [tex]T(n/3)[/tex] قرار

داده لذا در معادله جدید اگر بنابر قاعده : [tex]T(n)=aT(n/b) C.F(n)[/tex] پیش برویم داریم [tex]n^{log a} < O(n^{\sqrt{lgn}})[/tex] پس عبارت [tex]\theta (n^{\sqrt{lgn}})[/tex] مرتبه زمانی مد نظر هست

---

[tex]\sqrt{n}[/tex] کمتر از [tex]n/2[/tex] هستش لذا بین دو عبارت بعدی [tex]a=1< (b=2)^{(k=1)}[/tex] پس داریم :

[tex]T(n)=\theta (n^{k})=\theta (n)[/tex]

سلام.
دومی که خیلی سادس. نه درخت میخواد نه لازمه با روشای دیگه حلش کنید. جمع ۳ تا عبارته که بزرگترین مرتبه تو این چند جمله ای به عنوان تتا مرتبش در نظر گرفته میشه. رشد رادیکال n که خیلی آهسته تر از nدومه و از دور خارج میشه. n دوم هم از مرتبه nه . آخریشم که nه دیگه. یعنی کلاً از مرتبه n در میاد.