01 Fundamentals_modified.pdf

ci:i..:, as, o --=:i Univcr, ill:y of J-edd111t-...

ci:i..:, as, o --=:i Univcr, ill:y of J-edd111t- Topic 1 Fundamentals of the Analysis of Algorithm Efficiency Prof. Hanan Elazhary http:.!/computing. uj.edu.sa Main source: A. Levitin, Introduction to the Design and Analysis of Algorithms, 3rd edition  What is an algorithm? ci:i..:, as, o --=:i Univcr, ill:y of J-edd111t- An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., obtaining the required output for any legitimate input in a finite amount of time problem l algorithm input “computer” output http:.!/computing. uj.edu.sa 2  What is an algorithm?, Contd. Properties of an algorithm Representable in various forms Unambiguity/clearness Correctness Finiteness/termination Effectiveness 3  Historical Perspective Muhammad ibn Musa al-Khwarizmi – 9th century mathematician www.lib.virginia.edu/science/parshall/khwariz.html The word ‘algorism’ (originally) and later ‘algorithm’ come from his name Euclid’s algorithm for finding the greatest common divisor (of two or more numbers) is good for introducing the notion of an algorithm 4  Euclid’s Algorithm Problem Find gcd(m,n), the greatest common divisor of two nonnegative, not both zero integers m and n e.g., gcd(60,24) = 12 and gcd(60,0) = 60 Euclid’s algorithm is based on repeated application of the equality gcd(m,n) = gcd(n, m mod n) until the second number becomes 0, which makes the problem trivial e.g., gcd(60,24) = gcd(24,12) = gcd(12,0) = 12 gcd(0,0) = ? 5  Euclid’s Algorithm, Contd. Two descriptions of Euclid’s algorithm Step 1 If n = 0, return m and stop; otherwise go to Step 2. Step 2 Divide m by n and assign the value of the remainder to r (temporary variable). Step 3 Assign the value of n to m and the value of r to n. Go to Step 1. while n ≠ 0 do r ← m mod n m←n n←r return m gcd(m,n) 6  Analysis of Algorithms Issues correctness time efficiency (how fast) space efficiency (how much memory required) optimality Approaches theoretical (mathematical) analysis empirical analysis algorithm visualization 7 Theoretical Analysis of Time Efficiency  Theoretical Analysis of Time Efficiency Time efficiency (running time estimate) is a function of input size It is analyzed by determining the count of the basic operation of the algorithm (number of repetitions) The basic operation is the one that contributes the most towards the running time of the algorithm (typically, it is the most time-consuming operation in the algorithm’s innermost loop) Note that different basic operations may give different results! 9  Input Size and Basic Operation Examples Problem Input size Basic operation Searching for a key in a list of n items Number of list’s items, i.e., n Comparison of the key Matrix dimensions or total Multiplication of two matrices Multiplication of two numbers number of elements Checking primality of a given integer Size of n = number of digits in Division n (can only be divided by itself or by 1) binary representation Number of vertices and/or Visiting a vertex or traversing Typical graph problem edges an edge 10  Basic Operation Count Worst, Best and Average Cases For some algorithms, the time efficiency can be different for different inputs of the same size (due to difference in basic operation count) Worst case: Cworst(n) – maximum over inputs of size n Best case: Cbest(n) – minimum over inputs of size n Average case: Cavg(n) – average over inputs of size n Average refers to basic operation count required for an input (of size n), on average NOT the average of worst and best cases 11  Example: Sequential Search Worst case: n comparisons Based on the sum of Best case: 1 comparison, assuming K is in A natural numbers, Average case: (n+1)/2 comparisons, assuming K is in A (1+2+3+….+N)/N = (N(N+1)/2)/N = (N+1)/2 12 Types of Formulas for Basic Operation Count Exact formula e.g., C(n) = n(n-1)/2 Formula indicating order of growth with specific multiplicative constant e.g., C(n) ≈ 0.5n2 Formula indicating order of growth with unknown multiplicative constant e.g., C(n) ≈ cn2 13 Types of Formulas for Basic Operation Count. Contd. Order of growth of an algorithm indicates how slow/fast the algorithm will change if the input size is changed For example, if the order of growth is cn2 How much faster will the algorithm run on a computer that is twice as fast? How much longer does it take to solve the problem with double input size? taking into consideration that for small values of n, the order of growth does not really matter for large values of n, the order of growth is defined within a constant multiple as n→∞ 14 Values of Some Important Functions as n→∞ indicating the order of growth 15 Asymptotic Order of Growth of an Algorithm A way of comparing functions that ignores small input sizes and constant factors (because?) t(n) is in O(g(n)) class of functions t(n) that grow no faster than g(n) f(n) is in Ω(g(n)) - omega class of functions t(n) that grow at least as fast as g(n) t(n) is in Θ(g(n)) - theta class of functions t(n) that grow at same rate as g(n) 16  O-notation Definition t(n) is in O(g(n)), denoted t(n)  O(g(n)), if t(n) is bounded above by some constant multiple of g(n) for all large n, i.e., there exist some positive constant c and some non-negative integer n0 such that t(n) ≤ c g(n) for every n ≥ n0 Examples 10n  O(n2) 10n ≤ 10n2 for n ≥ 1 or 10n ≤ n2 for n ≥ 10 5n+20  O(n) order of growth of t(n) ≤ order of growth of g(n) within a 5n+20 ≤ 10n for n ≥ 4 constant multiple 17  -notation Definition t(n) is in (g(n)), denoted t(n)  (g(n)), if t(n) is bounded below by some constant multiple of g(n) for all large n, i.e., there exist some positive constant c and some non-negative integer n0 such that t(n) ≥ c g(n) for every n ≥ n0 Exercises: prove the following 10n2  (n2) 0.3n2 - 2n  (n2) 0.1n3  (n2) 18  -notation Definition t(n) is in (g(n)), denoted t(n)  (g(n)), if t(n) is bounded both above and below by some constant multiples of g(n) for all large n, i.e., there exist some positive constants c1 and c2 and some non-negative integer n0 such that c2 g(n) ≤ t(n) ≤ c1 g(n) for every n ≥ n0 Exercises: prove the following 10n2  (n2) 0.3n2 - 2n  (n2) (1/2)n(n+1)  (n2) 19  Summary of Notations >= (g(n)), functions that grow at least as fast as g(n) = (g(n)), functions that grow at the same rate as g(n) g(n) 1 is because log a n = log b n / log b a logba is a constant Exponential functions an can have different orders of growth for different a’s ♦ order log n < order ,,«(a>O) < order