2-5 Linear Recurrences Hengfeng Wei hfwei@nju.edu.cn March26.,2020 Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences March26,20201/26
2-5 Linear Recurrences Hengfeng Wei hfwei@nju.edu.cn March 26, 2020 Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 1 / 26
Don't we already know how to use the "Master Theorem"? T(n)=al(n/b)+f(n) Linear recurrences which may arise in average-case analysis. Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences March26,20202/26
Don’t we already know how to use the “Master Theorem”? T(n) = aT(n/b) + f(n) Linear recurrences which may arise in average-case analysis. Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 2 / 26
an f(an-1;an-2;...;an-t)+g(n) recurrence type typical example first-order linear an nan-1-1 nonlinear am=1/(1+an-1） second-order linear an=0m-1十2an-2 nonlinear am=am-1an-2十Vam-2 variable coefficients am=nan-1+(n-1)am-2+1 tth order an=f(am-1,am-2,.,0n-t)】 full-history 0n=n十an-1十an-2..十a1 divide-and-conquer an=a1n/2」+afn/21十n Table 2.1 Classification of recurrences Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences March26,20203/26
an = f(an−1, an−2, . . . , an−t) + g(n) Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 3 / 26
Theorem(First-order Linear Recurrences with Constant Coefficients) T(n)=rT(n-1)+g(n)forn>0 with T(0)=a T(n)r"a+ i1 Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences March26,20204/26
Theorem (First-order Linear Recurrences with Constant Coefficients) T(n) = rT(n − 1) + g(n) for n > 0 with T(0) = a T(n) = r n a + Xn i=1 r n−i g(i) Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 4 / 26
Theorem (First-order Linear Recurrences) T(n)=InT(n-1)+yn for n>0 with T(0)=0 T(m)=+∑ Cj+1Tj+2·En 1≤j<n T(n)=2nT(n-1)+Un =En (En-1T(n-2)+Un-1)+Un InEn-1T(n-2)+Inyn-1 yn InEn-1(In-2T(n-3)yn-2)+InVn-1+yn =InIn-1In-2T(n-3)+TnEn-19n-2+Tnyn-1+Un Hengfeng Wei (hfwei&inju.edu.cn) 2-5 Linear Recurrences March26,20205/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) = xnT(n − 1) + yn = xn (xn−1T(n − 2) + yn−1) + yn = xnxn−1T(n − 2) + xnyn−1 + yn = xnxn−1 (xn−2T(n − 3) + yn−2) + xnyn−1 + yn = xnxn−1xn−2T(n − 3) + xnxn−1yn−2 + xnyn−1 + yn = . . . Hengfeng Wei (hfwei@nju.edu.cn) 2-5 Linear Recurrences March 26, 2020 5 / 26
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