2-5 Linear Recurrences Hengfeng Wei hfwei@nju.edu.cn March 26,2020 4口·￥①，43，t夏，里Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences farch26.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) 4口，1①，43，t夏，里0Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences farch26.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
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. 4口·￥①，43，t夏，里Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences farch26.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) 4口·￥①，43，t夏，里Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences farch26.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
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 aln/2]amn/21+n Table 2.1 Classification of recurrences 4口·1①，43，t夏，30Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences farch26.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+ =1 4口，1①，43，t夏，里0Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences farch26.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)=EnT(n-1)+yn for n>0 with T(0)=0 T(m)=n+∑ Cj+1Tj+2·En 1≤j<n 4口，1①，43，t夏，30Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences farch26.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)=+∑ Cj+1Tj+2·En 1≤j<n T(n)=2nT(n-1)+Un =2n (En-1T(n-2)+Un-1)+Un EnEn-1T(n -2)+inyn-1+yn InEn-1(In-2T(n-3)+Vn-2)+inUn-1+n =InIn-1In-2T(n-3)+TnEn-19n-2+Tnyn-1+Un 4口·￥①，43，t夏，里Q0 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+∑ Tj+1j+2·…En 1≤j<n 4口，1①，43，t夏，30Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences farch26.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
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) Un xncn-1·C1 xn-1··E1 EnCn-1··x1 summation factor 4口·￥①，43，t夏，里Q0 Hengfeng Wei (hfweixinju.edu.cn) 2-5 Linear Recurrences farch26.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