Theorem (First-order Linear Recurrences) T(n)=InT(n-1)+yn for n >0 with T(0)=0 T(m)=n+∑ 2j+1j+2·…En 1≤j<n T(n) T(n-1) Yn xncn-1·C1 En-1···E1 EnCn-1···x1 summation factor S(n) T(n) Enxn-1···C1 S(n)=S(n-1)+ Yn Enrn-1···1 Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences March26,20206/26
Theorem (First-order Linear Recurrences) T(n) = xnT(n − 1) + yn for n > 0 with T(0) = 0 T(n) = yn + X 1≤j<n yjxj+1xj+2 · · · xn T(n) xnxn−1 · · · x1 | {z } summation factor = T(n − 1) xn−1 · · · x1 + yn xnxn−1 · · · x1 S(n) ≜ T(n) xnxn−1 · · · x1 S(n) = S(n − 1) + yn xnxn−1 · · · x1 Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 6 / 26
T(m)=(1+)Tn-1)+2 for n>1 with T(1)=0 m 1n+1 xn=1+ →xnxn-1·…x1=n+1 T(n) T(n-1) 2 十 for n 1 n+1 2 n+1 T(n)T(1) n+1 +2 3≤k≤n+1 T(m)=2(n+1)(Hn+1- 3 ≈2mnn-1.846m Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences March26,20207/26
T(n) = (1 + 1 n )T(n − 1) + 2 for n > 1 with T(1) = 0 xn = 1 + 1 n = n + 1 n =⇒ xnxn−1 · · · x1 = n + 1 T(n) n + 1 = T(n − 1) n + 2 n + 1 for n > 1 T(n) n + 1 = T(1) 2 + 2 X 3≤k≤n+1 1 k T(n) = 2(n + 1)(Hn+1 − 3 2 ) ≈ 2n ln n − 1.846n Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 7 / 26
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/26
T(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
After-class Exercise m=a-)-2Ta+2(-2n-少）n≥0mr0=0 "On Random 2-3 Trees",Andrew C Yao,1978 Do It! Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences March26,20209/26
After-class Exercise T(n) = T(n−1)− 2T(n − 1) n +2 1 − 2T(n − 1) n , n > 0 with T(0) = 0 “On Random 2-3 Trees”, Andrew C Yao, 1978 Do It! Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 9 / 26
Higher-order Linear Recurrences an=x1an-1+x2an-2+·+xtan-t+gn for n≥t with a0,a1,·,at-1 Hengfeng Wei (hfwei&inju.edu.cn) 2-5 Linear Recurrences March26,202010/26
Higher-order Linear Recurrences an = x1an−1 + x2an−2 + · · · + xtan−t + gn for n ≥ t with a0, a1, · · · , at−1 Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 10 / 26