سلام.
ممنون میشم توضیح بدید چرا مرتبه زمانی تابع [tex]T(n)=T(n-1) \frac{n-1}{n(n 1)}[/tex] با شرط اولیه [tex]T(0)=0[/tex]میشه [tex]o(\sqrt{n})[/tex] ؟
من فکر می کنم اینطوری باشه :
[tex]\frac{n-1}{n(n 1)}=\theta(\frac{1}{n})[/tex]
پس رابطه به این شکل می شه :
[tex]T(n)=T(n-1) \theta(\frac{1}{n})[/tex]
بنابراین داریم :
[tex]T(n)=\frac{1}{1} \frac{1}{2} \frac{1}{3} \frac{1}{4} \frac{1}{5} ... \frac{1}{n}\: =\theta(\lg n)=o(n^{\frac{1}{2}}=\sqrt{n})[/tex]
سپاس فراوان