(۲۶ آبان ۱۳۹۵ ۰۷:۱۷ ب.ظ)Pure Liveliness نوشته شده توسط:  سلام.
به صورت بازگشتی برای [tex]T(n)[/tex] مینویسیم:
[tex]T(n)=8T(\frac{n}{2})+1=8[8T(\frac{n}{4})+1]+1=8^2T(\frac{n}{4})+8^1+8^0=...[/tex] تا کجا ادامه پیدا میکنه؟ تا وقتی که به شرط اولیه برسیم یعنی داخل تابع T بشه برابر با [tex]n=\sqrt{k}[/tex]. خب پس:
[tex]T(n)=8^3T(\frac{n}{8})+8^2+8^1+8^0=8^xT(\frac{n}{2^x})+...+8^2+8^1+8^0=8^xk+8^{x​-1}+...+8^1+8^0=k8^x+\sum^{x-1}_{i=0}8^i=k8^x+\frac{(8^{x+1}-1)}{8-1}[/tex]
اما x چی هست؟ [tex]\frac{n}{2^x}=\sqrt{k}\: \longrightarrow\: (\frac{n}{\sqrt{k}})=2^x\: \: \longrightarrow\: x=\log^{(\frac{n}{\sqrt{k}})}_2[/tex]
خب پس جمع اون سری میشه :[tex]k8^{\log_2(\frac{n}{\sqrt{k}})}+\frac{(8^{\log^{(\frac{n}{\sqrt{k}})}_2}-1)}{8-1}=\theta(k8^{\log_2^{(\frac{n}{\sqrt{k}})}})=\theta(k2^{\log^{(\frac{n}{\sqrt{k​}})^2}})=\theta(k(\frac{n}{\sqrt{k}})^3)[/tex]

سایر توابع هم به همین فرم محاسبه میشن.