Chapter 3 - Methods of Algorithm Analysis PDF

CSC645 – ALGORITHM ANALYSIS & DESIGN CHAPTER 3 – Methods of Algorithm Analysis Nur Azmina Mohamad Zamani Chapter Overview  Analysis of iterative algorithms Empirical Analysis  Analysis of recursive a...

CSC645 – ALGORITHM ANALYSIS & DESIGN CHAPTER 3 – Methods of Algorithm Analysis Nur Azmina Mohamad Zamani Chapter Overview  Analysis of iterative algorithms Empirical Analysis  Analysis of recursive algorithms Time Efficiency of Iterative Algorithms GENERAL PLAN FOR ANALYSIS 4. Set up a 3. Determine 5. Simplify sum for the 1. Decide on 2. Identify worst, the sum number of parameter n algorithm’s average, and using times the indicating basic best cases standard basic input size operation for input of formulas and operation is size n rules executed Summation Formulas & Rules Summation Formula of i EXAMPLE 1 Solution for EXAMPLE 1 σ𝑛−2 σ 𝑛−1 𝑖=0 𝑗=𝑖+1 1 = σ 𝑛−2 𝑖=0 𝑛 − 1 − 𝑖 + 1 + 1 1 = σ𝑛−2 𝑖=0 𝑛 − 1 − 𝑖 = σ𝑛−2 𝑖=0 𝑛 − σ 𝑛−2 𝑖=0 1 − σ 𝑛−2 𝑖=0 𝑖 (𝑛−2)(𝑛−2+1) = (n-2+1)(n) – (n-2+1)(1) – 2 (𝑛−2)(𝑛−2+1) = n(n-1) – (n-1) - 2 𝑛2 −𝑛−2𝑛+2 = (𝑛2 − 𝑛) − (𝑛 − 1) − 2 𝑛2 −3𝑛+2 = 𝑛2 -n– n+1- 2 𝑛2 −7𝑛+4 = ∈ θ(𝑛2 ) 2 EXERCISES EXAMPLE 2 Solution for EXAMPLE 2 1) Input size  n 2) Algorithm’s basic operation(s)  the comparison in while loop (n > 1) 3) The value of n is about halved on each repetition of the loop; the answer should be about log 2 𝑛. 4) Based on the formula of binary representation: b = (log 2 𝑛) + 1 5) Therefore, O(log n). *Note: This can also be solved using recurrence relations (recursive algorithm analysis) Time Efficiency of Recursive Algorithms GENERAL PLAN FOR ANALYSIS 4. Set up a 3. Determine recurrence 5. Solve the 1. Decide on 2. Identify worst, relation for the recurrence for parameter n algorithm’s average, and number of the order of indicating basic operation best cases for times the basic growth of its input size input of size n operation is solution executed Recurrence Relation for some Algorithm Recurrence Algorithm Big-Oh Solution T(n) = T(n/2) + 1 Binary search O(log n) T(n) = T(n-1) + 1 Sequential search O(n) T(n) = 2T(n/2) + 1 Tree Traversal O(n) T(n) = T(n-1) + n Selection sort (or other n2 O(n2) sorts) T(n) = 2T(n/2) + n Merge sort (average case – O(n log n) Quick sort) EXAMPLE 1 The recurrence relation for the algorithm is: T(n) = T(n – 1) + 1, T(1) = 0 Find the complexity of the algorithm. SOLUTION T(n) = T(n-1) + 1 T(n-1) = T((n-1)-1) + 1 = T(n-2) + 1 + 1 = T(n-2) + 1 = T(n-2) + 2 T(n-2) = T((n-2)-1) + 1 = T(n-3) + 1 + 2 = T(n-3) + 1 = T(n-3) + 3 Pattern: T(n) = T(n-k) + k where k = 1, 2, 3, … n-k = 1 k = n-1 Substitution: T(n) = T(n – (n-1)) + (n-1) = T(1) + (n-1) =0+n–1 = n – 1 ∈ O(n) EXAMPLE 2 The recurrence relation for the algorithm is: T(n) = 2T(n/2) + n, T(1) = 1 Find the complexity of the algorithm. SOLUTION T(n) = 2T(n/2) + n T(n/2) = 2T(n/2 * 1/2) + (n * 1/2) = 2[2T(n/4) + n/2] + n = 2T(n/4) + n/2 = 4T(n/4) + n + n = 4T(n/4) + 2n T(n/4) = 2T(n/4 * 1/2) + (n/2 * ½) = 4[2T(n/8) + n/4] + 2n = 2T(n/8) + n/4 = 8T(n/8) + n + 2n = 8T(n/8) + 3n Pattern: Substitution: T(n) = 2k T(n/2k) + kn T(n) = n T(1) + n log 2 𝑛 n/2k = 1 = n (1) + n log 2 𝑛 2k = n = n + n log 2 𝑛 ∈ θ(n log n) k = log 2 𝑛 Choose the slowest from the asymptotic efficiency class Reference  A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 8 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. EXERCISES