Chapter 2 - Analysis of Algorithm PDF

CSC645 – ALGORITHM ANALYSIS & DESIGN CHAPTER 2 – Fundamentals of Algorithm Analysis Nur Azmina Mohamad Zamani Chapter Overview  Algorithm analysis framework  Asymptotic notations  Asymptotic efficiency classes Algorithm Analysis  Pu...

CSC645 – ALGORITHM ANALYSIS & DESIGN CHAPTER 2 – Fundamentals of Algorithm Analysis Nur Azmina Mohamad Zamani Chapter Overview  Algorithm analysis framework  Asymptotic notations  Asymptotic efficiency classes Algorithm Analysis  Purpose: To investigate an algorithm’s efficiency with respect to resources. - after proving correctness of an algorithm, algorithm efficiency is another quality needed for an algorithm. TWO TYPES OF ALGORITHM EFFICIENCY: Time Efficiency/Complexity Indicates how fast the algorithm runs. Space Efficiency/Complexity Indicates how much extra memory the algorithm needs. Algorithm Analysis: Other Algorithm Issues/Quality Simpler algorithms are easier to understand and implement. Simplicity The generality of the problem solved by the algorithm and the set of inputs accepted. Generality Lower bounds – the algorithm will not use less than some limit on a resource. Optimality Finding better algorithm Two types of approaches can be used to cater the issues in analyzing an algorithm – Empirical analysis & Theoretical analysis. Algorithm Analysis: Types of Analysis Empirical Analysis Theoretical Analysis Defines algorithm efficiency by Defines algorithm efficiency in terms of measuring using time units. number of basic operation executed with related to its basic operation. Factors that affect an Algorithm Runtime Complexity Input size Computer performance Algorithm Analysis Framework: Measuring Input Size (Space Complexity) T(n) indicates the input size, n for some function T.  The bigger the input size, the longer it takes to solve the problem.  eg. The time taken to solve 5 items is shorter than solving 10 items.  Measuring size by the number of bits, b in the n’s binary representation: b = 𝐥𝐨𝐠 𝟐 𝒏 + 1 Algorithm Analysis Framework: Measuring Running Time (Time Complexity) How to measure?  Identify the most important operation of the algorithm called basic operation (contribute the most to the total of running time)  Eg. Comparisons in a sorting algorithm  Compute the number of times/repetition the basic operation is executed (operation counts) Example of Operation Counts: Insertion Sort Other Examples Theoretical Analysis of Time Efficiency  Time efficiency is analyzed by determining the number of repetitions of the basic operation as a function of input size , n. Basic operation Running time cop C(n) The operation Expressed as the execution the number that T(n) for some time/running of basic contributes function T on time of an operations as the most the input algorithm’s of a function of towards the size, n. a single n. algorithm operation. running time. Order of Growth: Table of Values Fastest growth rate Slowest growth rate  Growth Functions Other Constant Linear Logarithmic Quadratic Cubic Exponential Polynomials Growth is Growth is Growth T(n) = n2 T(n) = n3 Growth is T(n) = nk independent directly increases e.g., typical e.g., matrix extremely e.g., typical of the input proportional slowly in nested multiplication rapid and in more size, n to n compared to n loops (bubble possibly nested loops T(n) = c T(n) = cn T(n) = log(n) sort) impractical e.g., e.g., finding a e.g., finding T(n) = cn T(n) = n log(n) accessing particular particular e.g., Towers e.g., sorting array element array element array element of Hanoi (2n), using divide at known (linear search) (binary Fibonacci and conquer location, search) number (2n) approach assignment Graph of Growth Functions Worst-Case Efficiency  An input(s) of size n for which the algorithm runs the longest among all possible inputs of that size.  Cworst(n) – maximum over inputs of size n  How to determine? 1) Analyze the algorithm to see what kind of inputs yield the largest value of the basic operation’s count, Cworst(n) among all possible inputs of size n. 2) Compute the worst-case value Cworst(n).  For any instance of size n, the running time will not exceed Cworst(n); its running time on the worst-case inputs. Best-Case Efficiency  An input(s) of size n for which the algorithm runs the fastest among all possible inputs of that size.  Cbest(n) – minimum over inputs of size n  How to determine? 1) Determine the kind of inputs for which the count C(n) will be the smallest among all possible inputs of size n. [NOTE: best-case doesn’t mean the smallest input; but it means the input of size n for which the algorithm runs the fastest.] 2) Compute the value of Cbest(n). Average-Case Efficiency  Average time taken (number of times the basic operation will be executed) to solve all the possible instances (random) of the input.  NOT the average of worst and best case  Neither the worst-case analysis nor its best-case counterpart yields the necessary information about an algorithm’s behavior.  Cavg(n) – “average” over inputs of size n  How to determine?  Must make assumptions about possible inputs of size n. EXAMPLE: Determining Worst-Case, Best- Case and Average-Case for an Algorithm  There are no matching The first element in the Standard assumptions: elements or the list is equal to the Probability of a successful matching element search key: Cbest(n) = 1. search = p(0 ≤ p ≤ 1) happens to be the last Probability of the first match one in the list. occurring in the ith position of the list is the same for The algorithm makes every i. Worst-case Best-case Average-case the largest no. of key To find the average comparisons among all no. of key comparisons possible inputs of size Cavg(n) : n: Cworst(n) = n. Successful search: Probability of the first match occurring in the ith position of the list is p/n for every i, and the no. of comparisons made by the algorithm in such situation is obviously i. Unsuccessful search: No. of comparisons is n with the probability of such a search being (1 – p). [NOTE: formula on the next slide] Average-case Formula  If p = 1 (successful),  The average no. of key comparisons made by Sequential Search is (n + 1) / 2.  The algorithm will inspect, on average, about half of the list’s elements.  If p = 0 (unsuccessful),  The average no. of key comparisons will be n because the algorithm will inspect all n elements on all such inputs. Asymptotic Notations  ASYMPTOTIC DEFINITION  approaching a given value as an expression containing a variable tends to infinity  ASYMPTOTIC COMPLEXITY  Describe the growth rate of the time or space complexity with respect to input size  Not directly related to the exact running time  ASYMPTOTIC GROWTH is when n  ∞ , thus, highest order term is more important.  3 Types of notations to compare and rank Order of Growth:  Big Oh (O) notation provides an upper bound for the growth rate of the given function.  Big Theta (θ) notation is used when an algorithm is bounded both above and below by the same kind of function.  Big Omega (Ω) notation provides a lower bound. Asymptotic Notations (cont.) Big Theta Big Omega Big Oh notation notation notation A function t(n) is said A function t(n) is said A function t(n) is said to be in O(g(n)), to be in θ(g(n)), to be in Ω(g(n)), denoted t(n) ϵ O(g(n)), denoted t(n) ϵ θ(g(n)), denoted t(n) ϵ Ω(g(n)), if t(n) is bounded if t(n) is bounded both if t(n) is bounded above by some above and below by below by some constant multiple of some constant multiple constant multiple of g(n) for all large n, of g(n) for all large n, g(n) for all large n, i.e., if there exist some i.e., if there exist some i.e., if there exist some positive constant c and positive constant c1 and positive constant c and some nonnegative c2 and some some nonnegative integer n0 such that nonnegative integer n0 integer n0 such that t(n) ≤ cg(n) for all n ≥ such that c2g(n) ≤ t(n) t(n) ≥ cg(n) for all n ≥ n0. ≤ c1g(n) for all n ≥ n0. n0. Asymptotic Notations (cont.) Big-Oh Notation  measures the worst-case time complexity or longest amount of time an algorithm can possibly take to complete.  For a problem of size n:  a constant-time algorithm is "order 1": O(1)  a linear-time algorithm is "order n": O(n)  a quadratic-time algorithm is "order n squared": O(n2)  EXAMPLES:  3n + 2 = O(n)  NOT O(3n)!  2 log2 n + 10 = O(log n)  2n + 6n1/2 = O(n)  n2 + 10 = O(n2) Big-Theta Notation  measures the average-case time complexity Big-Omega Notation  measures the best-case time complexity Asymptotic Efficiency Classes  Limits for Comparing Order of Growth t(n) slower than g(n) Big-Oh t(n) ∈ O(g(n)) t(n) equals to g(n) Big-Theta t(n) ϵ θ(g(n)) t(n) faster than g(n) Big-Omega t(n) ϵ Ω(g(n)) Differentiation Rules – Limits Calculation (L’Hôpital’s Rule) EXAMPLES  EXAMPLE 1 Let t(n) = 25n2 + n and g(n) = n2 SOLUTION: 𝒕(𝒏) 𝟐𝟓𝒏𝟐 +𝒏 lim = lim 𝒏→∞ 𝒈(𝒏) 𝒏→∞ 𝒏𝟐 𝟓𝟎𝒏+𝟏 = lim 𝒏→∞ 𝟐𝒏 𝟓𝟎 = lim 𝒏→∞ 𝟐 = lim 25 𝒏→∞ = 25 > 0 Therefore, t(n) = g(n); t(n) ϵ θ(g(n))  25n2 + n ϵ θ(n2) EXAMPLES  EXAMPLE 2 Let t(n) = n2 and g(n) = log n4 SOLUTION: 𝒕(𝒏) 𝒏𝟐 𝒕(𝒏) 𝒏𝟐 lim = lim lim = lim 𝒏→∞ 𝒈(𝒏) 𝒏→∞ log 𝑛4 𝒏→∞ 𝒈(𝒏) 𝒏→∞ log 𝑛4 𝟐𝒏 = lim 𝟒𝒏𝟑 = lim 𝟏 𝒏→∞ 𝒏→∞ 𝟒 log𝟏𝟎 𝒆 𝒏𝟒 𝒏 ln 𝟏𝟎 𝟏 𝟐 = lim 𝒏𝟑 = lim 2n (𝑛4 ln 10) log10 𝒆 𝒏→∞ 𝒏→∞ 𝒏𝟒 𝟏 𝟐 = lim = 2 ln 10 lim 𝒏𝟓 log10 𝒆 𝒏→∞ 𝟒 𝒏→∞ 𝟏 = = ∞ 2 log10 𝒆 𝟏 = 2 log10 𝒆 =∞ Therefore, t(n) > g(n); t(n) ϵ Ω(g(n))  n2 ϵ Ω(log n4) Summary of Sorting Algorithm Complexity 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