CS483-04 Non-recursive and Recursive Algorithm Analysis

1 CS483-04 Non-recursive and Recursive AlgorithmAnalysisInstructor: Fei LiRoom 443 ST IIOffice hours:Tue. & Thur. 4:30pm - 5:30pm or by CS483 lifei/teaching/cs483_fall07/CS483 Design and Analysis of Algorithms1 Lecture 04, September 6, 2007 Outline Review and More Analysis of Non-recursive Algorithms Analysis of Recursive Algorithms ExamplesCS483 Design and Analysis of Algorithms2 Lecture 04, September 6, 2007 Review O(g(n)):={f(n)|there existpositive constantscandn0such that0 f(n) c g(n)for alln n0}.f(n) O(g(n))f(n)growno fasterthang(n). (g(n)):={f(n)|there existpositive constantscandn0such that0 c g(n) f(n)for alln n0}.f(n) (g(n))f(n)growsat least as fastasg(n). (g(n)):={f(n)|there existpositive constantsc1,c2, andn0such thatc1 g(n) f(n) c2 g(n)for alln n0}.

2 F(n) (g(n))f(n)growsat the same rateasg(n).CS483 Design and Analysis of Algorithms3 Lecture 04, September 6, 2007 Asymptotic Notationsc1g(n)c2g(n)f(n)f(n)f(n)n0n0n0n nncg(n)cg(n)f(n) (g(n))f(n) O(g(n))f(n) (g(n))CS483 Design and Analysis of Algorithms4 Lecture 04, September 6, 2007 Review Tools and techniques to get asymptotic notation L Hopital s ruleIflimn f(n) = limn g(n) = and the derivativesf andg exist, thenlimn f(n)g(n)= limn f (n)g (n) Stirling s formulan! 2 n(ne)nwhereeis the base of natural logarithm,e Design and Analysis of Algorithms5 Lecture 04, September 6, 2007 Exercises Alllogarithmicfunctionsloganbelong to thesame class (logn)no matterwhat the logarithmic basea >1is. Allpolynomialsof the samedegreekbelong to the same classaknk+ak 1nk 1+ +a1n+a0 (nk).

3 Exponentialfunctionsanhavedifferent ordersof growth fordifferenta s, ,2n/ (3n). lnn <(lnn)2< n < n < n lnn < n2< n3<2n< n!< nnCS483 Design and Analysis of Algorithms6 Lecture 04, September 6, 2007 Some Properties of Asymptotic Order of Growth Transitivity f(n) O(g(n))andg(n) O(h(n)) f(n) O(h(n)) f(n) (g(n))andg(n) (h(n)) f(n) (h(n)) f(n) (g(n))andg(n) (h(n)) f(n) (h(n)) Reflexivity f(n) O(f(n)) f(n) (f(n)) f(n) (f(n)) SymmetryandTranspose Symmetry f(n) (g(n))if and only ifg(n) (f(n)) f(n) O(g(n))if and only ifg(n) (f(n))CS483 Design and Analysis of Algorithms7 Lecture 04, September 6, 2007 Outline Review Analysis of Non-recursive Algorithms Analysis of Recursive Algorithms ExamplesCS483 Design and Analysis of Algorithms8 Lecture 04, September 6, 2007 Time Efficiency of Non-recursive Algorithms Decide on parameternindicatinginput size.

4 Identify Algorithm sbasic operation. Determineworst,average, andbestcases for input of sizen. Sumthe number ofbasic operationsexecuted. Simplifythe sum using standard formula and rules (see AppendixA).CS483 Design and Analysis of Algorithms9 Lecture 04, September 6, 2007 Time Efficiency of Non-recursive Algorithms Pui=l1 = 1 + 1 + + 1 = (u l) + 1. Pni=1i= 1 + 2 + +n=n(n+1)2 n22 (n2). Pni=1i2= 12+ 22+ +n2=n(n+1)(2n+1)6 n33 (n3). Pni=1ai= 1 +a+a2+ +an=an+1 1a 1, a6= Design and Analysis of Algorithms10 Lecture 04, September 6, 2007 Example1: Maximum Element Determine the value of the largest element in a given array. Input: An arrayA[0, , n 1]of real numbers. Output: The value of the largest element :MAXELEMENT(A[0, n 1])max=A[0]fori= 1ton 1do ifA[i]> maxthenmax=A[i]return(max)CS483 Design and Analysis of Algorithms11 Lecture 04, September 6, 2007 Example2: Element Uniqueness Problem Determine whether all the elements in a given array are distinct.

5 Input: An arrayA[0, .. , n 1]. Output: Returns true if all the elements inAare distinct and false :UNIQUEELEMENTS(A[0, n 1])fori= 0ton 2do forj=i+ 1ton 1do ifA[i] =A[j]then return(f alse)return(true)CS483 Design and Analysis of Algorithms12 Lecture 04, September 6, 2007 Example3: Matrix Multiplication Multiply2n-by-nmatrices by the definition-based Algorithm . Input:2n-by-nmatricesAandB. Output: MatrixC=A :MATRIXMULTI(A, B)fori= 0ton 1do forj= 0ton 1do C[i, j] = 0fork= 0ton 1doC[i, j] =C[i, j] +A[i, k] B[k, j]return(C)CS483 Design and Analysis of Algorithms13 Lecture 04, September 6, 2007 Example4: Counting Binary Bits Input: A positive decimal integern. Output: The number of binary digits inn s binary :COUNTBINARYBITS(n)count= 1whilen >1do count=count+ 1n= n/2 return(count)CS483 Design and Analysis of Algorithms14 Lecture 04, September 6, 2007 Outline Review Analysis of Non-recursive Algorithms Analysis of Recursive Algorithms ExamplesCS483 Design and Analysis of Algorithms15 Lecture 04, September 6, 2007 Recurrences Arecurrenceis an equation or inequality that describes afunctionin terms ofits value over a smaller value.

6 Example: Findn!CS483 Design and Analysis of Algorithms16 Lecture 04, September 6, 2007 Recurrences Arecurrenceis an equation or inequality that describes afunctionin terms of its value over asmaller value. Example: Findn! Non-recursive :1 2 3 nAlgorithm :FINDFACTORIAL- (n)factorial= 1fori= 1tondofactorial=factorial ireturn(factorial) Recurrence:f(n) =n f(n 1)CS483 Design and Analysis of Algorithms17 Lecture 04, September 6, 2007 Algorithm :FINDFACTORIAL- (n)ifn= 0then return(1)else return(n FindFactorial (n 1))CS483 Design and Analysis of Algorithms18 Lecture 04, September 6, 2007 Example: Counting Number of Bits Input: A positive decimal integern. Output: The number of binary digits inn s binary :NON-RECURSIVECOUNT(n)count= 1whilen >1do8<:count=count+ 1n= n/2 return(count) Algorithm :RECURSIVECOUNT(n)ifi= 1do return(1)else return(RecursiveCount( n/2 ) + 1)CS483 Design and Analysis of Algorithms19 Lecture 04, September 6, 2007 Example: Fibonacci Numbers Output: A sequence of numbersF0, F1, F2.

7 , Fn, ..such thatFn=8>> <>>:Fn 1+Fn 2,ifn >11,ifn= 10,ifn= Design and Analysis of Algorithms21 Lecture 04, September 6, 2007 Example: Fibonacci Numbers Output: A sequence of numbersF0, F1, F2, .. , Fn, ..such thatFn=8>> <>>:Fn 1+Fn 2,ifn >11,ifn= 10,ifn= :FIBNUMBER(n)ifn= 0return(0)ifn= 1return(1)else return(F ibNumber(n 1) +F ibNumber(n 2))CS483 Design and Analysis of Algorithms22 Lecture 04, September 6, 2007 Example: Hanoi Tower Problem Move all the disks from pegato pegc. Large disk cannot be on top of a smaller one. Input:ndisks in order of sizes on ,b, :HANOITOWER(n, a, c, b)ifn= 1 Move the disk fromatocelse8>> <>>:HanoiTower(n 1, a, b, c)Move the largest disk fromatocHanoiTower(n 1, b, c, a)CS483 Design and Analysis of Algorithms23 Lecture 04, September 6, 2007 Analysis of Recursive Algorithms The iteration method Expand (iterate) the recurrenceand express it as a summation of termsdepending only onnand the initial conditions.

8 The substitution method Master Theorem(To be introduced in Chapter4.)CS483 Design and Analysis of Algorithms24 Lecture 04, September 6, 2007 Iteration Method: Examples n!T(n) =T(n 1) + 1 Tower of HanoiT(n) = 2T(n 1) + 1CS483 Design and Analysis of Algorithms25 Lecture 04, September 6, 2007 Iteration: Example n!(T(n) =T(n 1) + 1)T(n) =T(n 1) + 1= (T(n 2) + 1) + 1=T(n 2) + 2 =T(n i) +i =T(0) +n=n Tower of Hanoi(T(n) = 2T(n 1) + 1)???CS483 Design and Analysis of Algorithms26 Lecture 04, September 6, 2007 Iteration: Example n!(T(n) =T(n 1) + 1) Tower of Hanoi(T(n) = 2T(n 1) + 1)T(n) = 2T(n 1) + 1= 2(2T(n 2) + 1) + 1= 22T(n 2) + 2 + 1 = 2iT(n i) + 2i 1+ + 1 = 2n 1T(1) + 2n 1+ 2n 1+ + 1= 2n 1T(1) +n 2Xi=02i= 2n 1+ 2n 1 1= 2n 1CS483 Design and Analysis of Algorithms27 Lecture 04, September 6, 2007 Assignment1 Problems1.

9 Prove or find a counter-example:(n3)n< n!<(n2)n,ifn p. 8, Exercises ( ) 5, p. 60, Exercises ( ) 5, 64. p. 67, Exercises ( ) 2, 45. p. 76, Exercises ( ) 1, 3, 5 Due date: September 20, 2007. In classCS483 Design and Analysis of Algorithms37 Lecture 04, September 6, 2007