(۲۹ مهر ۱۳۹۳ ۰۷:۴۹ ب.ظ)fatemeh69 نوشته شده توسط:  [tex]T(n)=T(n-1) \frac{a}{n}[/tex]
[tex]T(n-1)=T(n-2) \frac{a}{n-1}[/tex]
پس با جایگذاری خط دوم در فرمول خط اول داریم:
[tex]T(n)=T(n-2) \frac{a}{n-1} \frac{a}{n}[/tex]
دوباره می ریم T(n-2)رو حساب می کنیم و در فرمول جایگذاری می کنیم حاصل می شه:
[tex]T(n)=T(n-3) \frac{a}{n-2} \frac{a}{n-1} \frac{a}{n}[/tex]


و با جایگذاری های متعدد نهایتا به این می رسیم:
[tex]T(n)=T(1) \frac{a}{2} \frac{a}{3} .... \frac{a}{n-2} \frac{a}{n-1} \frac{a}{n}[/tex]
و خودمون T(1)رو a فرض می کنیم (خیلی هم مهم نیست چس فرض کنیم چون عدد ثابت تاثیری تو رتبه نداره)
حالا این بدست میاد:
[tex]T(n)=a \frac{a}{2} \frac{a}{3} .... \frac{a}{n-2} \frac{a}{n-1} \frac{a}{n}[/tex]
[tex]T(n)=a(1 \frac{1}{2} \frac{1}{3} \frac{1}{4} .... \frac{1}{n})[/tex]
طبق تعریف می دانیم که حاصل عبارت داخل پرانتز Lnn است (این تعریفه و ما همین طوری قلفتی ازش استفاده می کنیم و اثباتش مهم نیست اثباتش رو بچه های ریاضی می دونن نیازی به محاسبه سیگما نیست)
پس کل عبارت می شه:
[tex]T(n)=a(Lnn)[/tex]
[tex]T(n)=\theta(Lnn)[/tex]