Question

快速排序时间复杂度递推式求通项公式~

Answer 1

两边同除以n(n+1)得到

C(n)/(n+1) = 2/(n+1) + C(n-1)/n

然后取n=1,2,...求和得到

C(n)/(n+1) = 2(1/2+...+1/(n+1)) + O(1) = 2lnn + O(1)

所以C(n)=2nlnn + O(n)