CS245-2014S-0 2 Algorithm Analysis 102-0: Algorithm AnalysisWhen is algorithm A better than algorithm B?02-1: Algorithm AnalysisWhen is algorithm A be tter than algorithm B?• Algorithm A runs faster02-2: Algorithm AnalysisWhen is algorithm A be tter than algorithm B?• Algorithm A runs faster• Algorithm A requires less space to run02-3: Algorithm AnalysisWhen is algorithm A be tter than algorithm B?• Algorithm A runs faster• Algorithm A requires less space to runSpace / Time Trade-off• Can often create an algorithm that runs faster, by using more spaceFor now, we will concentrate on time efficiency02-4: Best Case vs. Worst CaseHow long does the following function take to run:boolean find(int A[], int element) {for (i=0; i<A.length; i++) {if (A[i] == elem)return true;}return false;}02-5: Best Case vs. Worst CaseHow long does the following function take to run:boolean find(int A[], int element) {for (i=0; i<A.length; i++) {if (A[i] == elem)return true;}return false;}It depends on if – and where – the element is in the list 02-6: Best Case vs. Worst Case• Best Case – What is the fastest th a t the algorithm can run• Worst Case – What is the slowest that the algorithm can run• Average Case – How long, on average, does the algorithm take to runCS245-2014S-0 2 Algorithm Analysis 2Worst Case performance is almost always important.Usually, Best Case pe rformance is unimportant (why?)Usually, Average Case = Worst Case (but not always!)02-7: Measuring Time EfficiencyHow long does a n algorithm ta ke to run?02-8: Measuring Time EfficiencyHow long does a n algorithm ta ke to run?• Implement on a computer, time using a stopwatch.02-9: Measuring Time EfficiencyHow long does a n algorithm ta ke to run?• Implement on a computer, time using a stopwatch.Problems:• Not just te sting algorithm – testing implementation of algorithm• Implementation details (cache performance, other pro grams running in the background, etc) can affectresults• Hard to c ompare algorithms that are not te sted under exactly the same conditions02-10: Measuring Time EfficiencyHow long does a n algorithm ta ke to run?• Implement on a computer, time using a stopwatch.Problems:• Not just te sting algorithm – testing implementation of algorithm• Implementation details (cache performance, other pro grams running in the background, etc) can affectresults• Hard to c ompare algorithms that are not te sted under exactly the same conditions• Better Method: Build a mathematical model of the r unning tim e, use model to compare algorithms02-11: Competing Algorithms• Linear Searchfor (i=low; i <= high; i++)if (A[i] == elem) return true;return false;• Binary Sear c hint BinarySearch(int low, int high, elem) {if (low > high) return false;mid = (high + low) / 2;if (A[mid] == elem) return true;if (A[mid] < elem)return BinarySearch(mid+1, high, elem);elsereturn BinarySearch(low, mid-1, elem);}CS245-2014S-0 2 Algorithm Analysis 302-12: Linear vs Binary• Linear Searchfor (i=low; i <= high; i++)if (A[i] == elem) return true;return false;Time Required, f or a problem of size n (worst case):02-13: Linear vs Binary• Linear Searchfor (i=low; i <= high; i++)if (A[i] == elem) return true;return false;Time Required, f or a problem of size n (worst case):c1∗ n for some constant c102-14: Linear vs Binary• Binary Sear c hint BinarySearch(int low, int high, elem) {if (low > high) return false;mid = (high + low) / 2;if (A[mid] == elem) return true;if (A[mid] < elem)return BinarySearch(mid+1, high, elem);elsereturn BinarySearch(low, mid-1, elem);}Time Required, f or a problem of size n (worst case):02-15: Linear vs Binary• Binary Sear c hint BinarySearch(int low, int high, elem) {if (low > high) return false;mid = (high + low) / 2;if (A[mid] == elem) return true;if (A[mid] < elem)return BinarySearch(mid+1, high, elem);elsereturn BinarySearch(low, mid-1, elem);}CS245-2014S-0 2 Algorithm Analysis 4Time Required, f or a problem of size n (worst case): c2∗ lg(n) for som e constant c202-16: Do Constants Matter?• Linear Search requires time c1∗ n, for some c1• Binary Sear c h requires time c2∗ lg(n), for some c2What if there is a very high overhead cost fo r function calls?What if c2is 1000 times larger than c1?02-17: Constants Do Not Matter!Length of list Time Required for Time Required forLinear Search Binary Search10 0.001 seconds 0.3 seconds100 0.01 seconds 0.66 second s1000 0.1 seconds 1.0 seconds10000 1 second 1.3 seconds100000 10 seconds 1.7 seco nds1000000 2 minutes 2.0 seconds10000000 17 minutes 2.3 seconds101011 days 3.3 seconds101530 centuries 5.0 seconds1020300 million years 6.6 seconds02-18: Growth RateWe care about the Growth Rate of a f unction – how much more we c a n do if we add more processing powerFaster Computers 6= Solving Problems FasterFaster Computers = Solving Larger Problems• Modeling m ore variables• Handling b igger databases• Pushing more polygons02-19: Growth Rate ExamplesSize of problem th a t can be solvedtime 10n 5n n lg n n2n32n1 s 1000 2000 100 3 100 21 132 s 2000 4000 184 3 141 27 1420 s 2000 0 40000 14470 447 58 171 m 60000 120000 39311 774 84 191 hr 3600000 7200000 1736782 18973 331 2502-20: Constants and Running Times• When calculating a formula for the r unning tim e of an algorithm:• Constants aren’t as important as the growth rate of the function• Lower order terms don ’t have much of an impact on the growth rate• x3+ x vs x3• We’d like a formal method for describing what is important when analyzing running time, and what is not.CS245-2014S-0 2 Algorithm Analysis 502-21: Big-Oh NotationO(f (n)) is the set of all functions tha t are bound f rom above by f (n)T (n) ∈ O(f (n)) if∃c, n0such that T (n) ≤ c ∗ f(n) when n > n002-22: Big-Oh Examplesn ∈ O(n) ?10n ∈ O(n) ?n ∈ O(10n) ?n ∈ O(n2) ?n2∈ O(n) ?10n2∈ O(n2) ?n lg n ∈ O(n2) ?ln n ∈ O(2n) ?lg n ∈ O(n) ?3n + 4 ∈ O(n) ?5n2+ 10n − 2 ∈ O(n3)? O(n2) ? O(n) ?02-23: Big-Oh Examplesn ∈ O(n)10n ∈ O(n)n ∈ O(10n)n ∈ O(n2)n26∈ O(n)10n2∈ O(n2)n lg n ∈ O(n2)ln n ∈ O(2n)lg n ∈ O(n)3n + 4 ∈ O(n)5n2+ 10n − 2 ∈ O(n3),∈ O(n2), 6∈ O(n) ?02-24: Big-Oh Examples II√n ∈ O(n) ?lg n ∈ O(2n) ?lg n ∈ O(n) ?n lg n ∈ O(n) ?n lg n ∈ O(n2) ?√n ∈ O(lg n) ?lg n ∈ O(√n) ?n lg n ∈ O(n32) ?n3+ n lg n + n√n ∈ O(n lg n) ?n3+ n lg n + n√n ∈ O(n3) ?n3+ n lg n + n√n ∈ O(n4) ?02-25: Big-Oh Examples IICS245-2014S-0 2