T(n)=(1+)T(n-1)+2forn>1 with T(1)=0 T(m)=2(n+1)(H+1- 3 ≈2nnn-1.846m Tm=m+1)+2∑(r6-1)+Tn-） 1≤i≤n for n >1 with T(0)=T(1)=0 average number of comparisons of QUICKSORT Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences March26,20208/26T(n) = (1 + 1 n )T(n − 1) + 2 for n > 1 with T(1) = 0 T(n) = 2(n + 1)(Hn+1 − 3 2 ) ≈ 2n ln n − 1.846n T(n) = (n + 1) + 1 n X 1≤i≤n  T(i − 1) + T(n − i)  for n > 1 with T(0) = T(1) = 0 average number of comparisons of Quicksort Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 8 / 26