Review of last class,Asymptotic notations Mathematical Background Analysis of non-recursive algorithms,2018/10/20,2,2015-2016-01 Design and Analysis of Algorithm SCUN,Fundamentals of the Analysis of Algorithm Efficiency (III),Chapter 2,1、 Analysis of recursive algorithms 2、 Fibonacci numbers,2018/10/20,4,2015-2016-01 Design and Analysis of Algorithm SCUN,Goals of this lecture,At the end of this lecture, you should Master the plan for analysis of recursive algorithm Master the methods for solving recurrence relations Be familiar with Fibonacci number,2018/10/20,5,2015-2016-01 Design and Analysis of Algorithm SCUN,Plan for Analysis of Recursive Algorithms,Decide on a parameter indicating an inputs size.,Identify the algorithms basic operation.,Check whether the number of times the basic op. is executed may vary on different inputs of the same size. (If it may, the worst, average, and best cases must be investigated separately.),Set up a recurrence relation with an appropriate initial condition expressing the number of times the basic op. is executed.,Solve the recurrence (or, at the very least, establish its solutions order of growth) by backward substitutions or another method.,2018/10/20,6,2015-2016-01 Design and Analysis of Algorithm SCUN,Recurrence Relations,A recurrence relation can be put into an equivalent closed form without the recursion Generation function Characteristics equation Substitution,A recurrence relation is a recursive form of an equation, for example:,2018/10/20,7,2015-2016-01 Design and Analysis of Algorithm SCUN,Example 4: Recursive evaluation of n!,Definition: n ! = 1 2 (n-1) n for n 1 and 0! = 1,Input size:,Basic operation:,Best, worst, average case:,Recurrence relation:,n,Multiplication,no,T(n) = T(n-1) + 1,Recursive definition of n!: F(n) = F(n-1) n for n 1 and F(0) = 1, T(0) = 0,2018/10/20,8,2015-2016-01 Design and Analysis of Algorithm SCUN,Solving the recurrence for T(n),T(n) = T(n-1) + 1, T(0) = 0 Begin by looking at a series of equations with decreasing values of n:,2018/10/20,9,2015-2016-01 Design and Analysis of Algorithm SCUN,Then, we substitute back into the first equation:,Solving the recurrence for T(n) (cont.),2018/10/20,10,2015-2016-01 Design and Analysis of Algorithm SCUN,We stop when we get to T(0):,Solving the recurrence for T(n) (cont.),How many “+1” terms are there? Notice we increase them with each substitution.,2018/10/20,11,2015-2016-01 Design and Analysis of Algorithm SCUN,We must have n of the “+ 1” terms because we,Solving the recurrence for T(n) (cont.),So, our closed form of the equation is:,2018/10/20,12,2015-2016-01 Design and Analysis of Algorithm SCUN,Example 5: The Tower of Hanoi Puzzle,Recurrence for number of moves:,2018/10/20,13,2015-2016-01 Design and Analysis of Algorithm SCUN,Solving recurrence for number of moves,M(n) = 2M(n-1) + 1, M(1) = 1,2018/10/20,14,2015-2016-01 Design and Analysis of Algorithm SCUN,Example 6: Counting #bits,Input size:,Basic operation:,Best, worst, average case:,Recurrence relation:,n,Addition,no,A(n) = A(n/2) +1 A(1) = 0,Closed form:,2018/10/20,15,2015-2016-01 Design and Analysis of Algorithm SCUN,Example 7 Fibonacci numbers,The Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, ,The Fibonacci recurrence: F(n) = F(n-1) + F(n-2) F(0) = 0 F(1) = 1,General homogeneous 2nd order linear recurrence with constant coefficients:aX(n) + bX(n-1) + cX(n-2) = 0,2018/10/20,16,2015-2016-01 Design and Analysis of Algorithm SCUN,Solving aX(n) + bX(n-1) + cX(n-2) = 0,Set up the characteristic equation (quadratic)ar2 + br + c = 0,Solve to obtain roots r1 and r2,General solution to the recurrence if r1 and r2 are two distinct real roots: X(n) = r1n + r2n if r1 = r2 = r are two equal real roots: X(n) = rn + nr n,Particular solution can be found by using initial conditions,2018/10/20,17,2015-2016-01 Design and Analysis of Algorithm SCUN,Application to the Fibonacci numbers,Characteristic equation:,r2 - r - 1=0,F(n) = F(n-1) + F(n-2) or F(n) - F(n-1) - F(n-2) = 0,Roots of the characteristic equation:,General solution to the recurrence:,Particular solution for F(0) =0, F(1)=1:,2018/10/20,18,2015-2016-01 Design and Analysis of Algorithm SCUN,Computing Fibonacci numbers,Definition-based recursive algorithm,ALGORITHM F(n)/Input: A nonnegative integer n/Output: The nth Fibonacci numberif n 1 return nelse return F(n-1) + F(n-2),Input size:,Basic operation:,Best, worst, average case:,Recurrence relation:,n,Addition,no,A(n) = A(n-1) + A(n-2) +1 A(0) = 0, A(1) =0,Closed form:,2018/10/20,19,2015-2016-01 Design and Analysis of Algorithm SCUN,Computing Fibonacci numbers,Explicit formula algorithm,ALGORITHM Fib(n)/Input: A nonnegative integer n/Output: The nth Fibonacci numberF0 0; F1 0for i 2 to n doFi Fi-1 + Fi-2 return F(n),Nonrecursive definition-based algorithm,