Analysis of Algorithms Input 2010 Goodrich Tamassia Algorithm Analysis of Algorithms Output 1 Running Time Most algorithms transform input objects into output objects The running time of an algorithm typically grows with the input size Average case time is often difficult to determine We focus on the worst case running time Easier to analyze Crucial to applications such as games finance and robotics 2010 Goodrich Tamassia best case average case worst case 120 100 Running Time 80 60 40 20 0 1000 Analysis of Algorithms 2000 3000 4000 I nput Size 2 Experimental Studies Write a program implementing the algorithm Run the program with inputs of varying size and composition Use a method like clock to get an accurate measure of the actual running time Plot the results 2010 Goodrich Tamassia 9000 8000 7000 Time ms 6000 5000 4000 3000 2000 1000 0 0 Analysis of Algorithms 50 100 I nput Size 3 Limitations of Experiments It is necessary to implement the algorithm which may be difficult Results may not be indicative of the running time on other inputs not included in the experiment In order to compare two algorithms the same hardware and software environments must be used 2010 Goodrich Tamassia Analysis of Algorithms 4 Theoretical Analysis Uses a high level description of the algorithm instead of an implementation Characterizes running time as a function of the input size n Takes into account all possible inputs Allows us to evaluate the speed of an algorithm independent of the hardware software environment 2010 Goodrich Tamassia Analysis of Algorithms 5 Pseudocode Example find High level description max element of of an algorithm an array More structured than Algorithm arrayMax A n English prose Input array A of n integers Less detailed than a Output maximum element of A program Preferred notation for currentMax A 0 describing algorithms for i 1 to n 1 do Hides program if A i currentMax then design issues currentMax A i return currentMax 2010 Goodrich Tamassia Analysis of Algorithms 6 Pseudocode Details Control flow if then else while do repeat until for do Indentation replaces braces Method declaration Algorithm method arg arg Input Output 2010 Goodrich Tamassia Method call var method arg arg Return value return expression Expressions Assignment like in C Equality testing like in C n2 Superscripts and other mathematical formatting allowed Analysis of Algorithms 7 The Random Access Machine RAM Model A CPU A potentially unbounded bank of memory cells each of which can hold an arbitrary number or character 2 1 0 Memory cells are numbered and accessing any cell in memory takes unit time 2010 Goodrich Tamassia Analysis of Algorithms 8 Seven Important Functions Seven functions that often appear in algorithm analysis Constant 1 Logarithmic log n Linear n N Log N n log n Quadratic n2 Cubic n3 Exponential 2n In a log log chart the slope of the line corresponds to the growth rate 2010 Goodrich Tamassia Analysis of Algorithms 9 Functions Graphed Using Normal Scale Slide by Matt Stallmann included with permission g n 1 g n n lg n g n 2n g n n2 g n lg n g n n 2010 Stallmann g n n3 Analysis of Algorithms 10 Primitive Operations Basic computations performed by an algorithm Identifiable in pseudocode Largely independent from the programming language Exact definition not important we will see why later Assumed to take a constant amount of time in the RAM model 2010 Goodrich Tamassia Analysis of Algorithms Examples Evaluating an expression Assigning a value to a variable Indexing into an array Calling a method Returning from a method 11 Counting Primitive Operations By inspecting the pseudocode we can determine the maximum number of primitive operations executed by an algorithm as a function of the input size Algorithm arrayMax A n currentMax A 0 for i 1 to n 1 do if A i currentMax then currentMax A i increment counter i return currentMax 2 2n 2 n 1 2 n 1 2 n 1 1 Total 8n 2 2010 Goodrich Tamassia Analysis of Algorithms 12 Estimating Running Time Algorithm arrayMax executes 8n 2 primitive operations in the worst case Define a Time taken by the fastest primitive operation b Time taken by the slowest primitive operation Let T n be worst case time of arrayMax Then a 8n 2 T n b 8n 2 Hence the running time T n is bounded by two linear functions 2010 Goodrich Tamassia Analysis of Algorithms 13 Growth Rate of Running Time Changing the hardware software environment Affects T n by a constant factor but Does not alter the growth rate of T n The linear growth rate of the running time T n is an intrinsic property of algorithm arrayMax 2010 Goodrich Tamassia Analysis of Algorithms 14 Slide by Matt Stallmann included with permission Why Growth Rate Matters if runtime is time for n 1 time for 2 n time for 4 n c lg n c lg n 1 c lg n 1 c lg n 2 cn c n 1 2c n 4c n c n lg n cn 2c n lg n 2cn 4c n lg n 4cn c n2 c n2 2c n 4c n2 16c n2 c n3 c n3 3c n2 8c n3 64c n3 c 2n c 2 n 1 c 2 2n c 2 4n c n lg n 2010 Stallmann Analysis of Algorithms runtime quadruple s when problem size doubles 15 Comparison of Two Algorithms Slide by Matt Stallmann included with permission insertion sort is n2 4 merge sort is 2 n lg n sort a million items insertion sort takes roughly 70 hours while merge sort takes roughly 40 seconds This is a slow machine but if 100 x as fast then it s 40 minutes versus less than 0 5 seconds 2010 Stallmann Analysis of Algorithms 16 Constant Factors The growth rate is not affected by constant factors or lower order terms Examples T n 102n 105 is a linear function 105n2 108n is a quadratic function 1E 26 1E 24 1E 22 1E 20 1E 18 1E 16 1E 14 1E 12 1E 10 1E 8 1E 6 1E 4 1E 2 1E 0 1E 0 Quadratic Quadratic Linear Linear 1E 2 1E 4 1E 6 1E 8 1E 10 n 2010 Goodrich Tamassia Analysis of Algorithms 17 Big Oh Notation 10 000 Given functions f n and g n we say that 1 000 f n is O g n if there are positive constants 100 c and n0 such that 3n 2n 10 n f n cg n for n n0 Example 2n 10 is O n 2n 10 cn c 2 n 10 n 10 c 2 Pick c 3 and n0 10 2010 Goodrich Tamassia 10 1 1 Analysis of Algorithms 10 n 100 1 000 18 Big Oh Example 1 000 000 Example the function n2 is not O n n 2 100n 100 000 10n n 10 000 n2 cn 1 000 n c The above 100 inequality cannot be satisfied since c 10 must be a constant 1 1 2010 Goodrich Tamassia Analysis of Algorithms 10 n 100 1 000 19 More Big …