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