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


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