CSE332: Data AbstractionsLecture 3: Asymptotic AnalysisDan GrossmanSpring 2010Comparing algorithmsWhen is one algorithm (not implementation) better than another?– Various possible answers (clarity, security, …)– But a big one is performance: for sufficiently large inputs, runs in less time (our focus) or less spaceLarge inputs because probably any algorithm is “plenty good” for small inputs (if n is 10, probably anything is fast)Answer will be independent of CPU speed, programming language, coding tricks, etc.Answer is general and rigorous, complementary to “coding it up and timing it on some test cases”– Can do analysis before coding!Spring 2010 2CSE332: Data AbstractionsAnalyzing code (“worst case”)Basic operations take “some amount of” constant time– Arithmetic (fixed-width)– Assignment– Access one Java field or array index–Etc.(This is an approximation of reality: a very useful “lie”.)Consecutive statements Sum of timesConditionals Time of test plus slower branchLoops Sum of iterationsCalls Time of call’s bodyRecursion Solve recurrence equationSpring 2010 3CSE332: Data AbstractionsExampleFind an integer in a sorted arraySpring 2010 4CSE332: Data Abstractions2351637507375126// requires array is sorted // returns whether k is in arrayboolean find(int[]arr, int k){???}Linear searchFind an integer in a sorted arraySpring 2010 5CSE332: Data Abstractions2351637507375126// requires array is sorted // returns whether k is in arrayboolean find(int[]arr, int k){for(int i=0; i < arr.length; ++i)if(arr[i] == k)return true;return false;}Best case: 6ish steps = O(1)Worst case: 6ish*(arr.length) = O(arr.length)Binary searchFind an integer in a sorted array– Can also be done non-recursively but “doesn’t matter” hereSpring 2010 6CSE332: Data Abstractions2351637507375126// requires array is sorted // returns whether k is in arrayboolean find(int[]arr, int k){return help(arr,k,0,arr.length);}boolean help(int[]arr, int k, int lo, int hi) {int mid = (hi+lo)/2; //i.e., lo+(hi-lo)/2if(lo==hi) return false;if(arr[mid]==k) return true;if(arr[mid]< k) return help(arr,k,mid+1,hi);else return help(arr,k,lo,mid);}Binary searchSpring 2010 7CSE332: Data Abstractions// requires array is sorted // returns whether k is in arrayboolean find(int[]arr, int k){return help(arr,k,0,arr.length);}boolean help(int[]arr, int k, int lo, int hi) {int mid = (hi+lo)/2;if(lo==hi) return false;if(arr[mid]==k) return true;if(arr[mid]< k) return help(arr,k,mid+1,hi);else return help(arr,k,lo,mid);}Best case: 8ish steps = O(1)Worst case: T(n) = 10ish + T(n/2) where n is hi-lo• O(log n) where n is array.length•Solve recurrence equation to know that…Solving Recurrence Relations1. Determine the recurrence relation. What is the base case?– T(n) = 10 + T(n/2) T(1) = 82. “Expand” the original relation to find an equivalent general expression in terms of the number of expansions.– T(n) = 10 + 10 + T(n/4)= 10 + 10 + 10 + T(n/8)= …= 10k + T(n/(2k))3. Find a closed-form expression by setting the number of expansions to a value which reduces the problem to a base case– n/(2k) = 1 means n = 2k means k = log2n–So T(n) = 10 log2n + 8 (get to base case and do it)–So T(n) is O(log n)Spring 2010 8CSE332: Data AbstractionsIgnoring constant factors• So binary search is O(log n) and linear is O(n)– But which is faster• Could depend on constant factors–How many assignments, additions, etc. for each n– And could depend on size of n• But there exists some n0such that for all n > n0binary search wins• Let’s play with a couple plots to get some intuition…Spring 2010 9CSE332: Data AbstractionsExample• Let’s try to “help” linear search– Run it on a computer 100x as fast (say 2010 model vs. 1990)– Use a new compiler/language that is 3x as fast– Be a clever programmer to eliminate half the work– So doing each iteration is 600x as fast as in binary search• Note: 600x still helpful for problems without logarithmic algorithms!Spring 2010 10CSE332: Data AbstractionsAnother example: sum arrayTwo “obviously” linear algorithms: T(n) = O(1) + T(n-1)Spring 2010 11CSE332: Data Abstractionsint sum(int[] arr){int ans = 0;for(int i=0; i<arr.length; ++i)ans += arr[i]; return ans;}int sum(int[] arr){return help(arr,0);}int help(int[]arr,int i) {if(i==arr.length) return 0;return arr[i] + help(arr,i+1);}Recursive:– Recurrence is k + k + … + kfor n timesIterative:What about a binary version?Spring 2010 12CSE332: Data AbstractionsRecurrence is T(n) = O(1) + 2T(n/2)– 1 + 2 + 4 + 8 + … for log n times–2(log n)– 1 which is proportional to n (definition of logarithm)Easier explanation: it adds each number once while doing little else“Obvious”: You can’t do better than O(n) – have to read whole arrayint sum(int[] arr){return help(arr,0,arr.length);}int help(int[] arr, int lo, int hi) {if(lo==hi) return 0;if(lo==hi-1) return arr[lo]; int mid = (hi+lo)/2;return help(arr,lo,mid) + help(arr,mid,hi);}Parallelism teaser• But suppose we could do two recursive calls at the same time– Like having a friend do half the work for you!Spring 2010 13CSE332: Data Abstractionsint sum(int[]arr){return help(arr,0,arr.length);}int help(int[]arr, int lo, int hi) {if(lo==hi) return 0;if(lo==hi-1) return arr[lo]; int mid = (hi+lo)/2;return help(arr,lo,mid) + help(arr,mid,hi);}• If you have as many “friends of friends” as needed the recurrence is now T(n) = O(1) + 1T(n/2)– O(log n) : same recurrence as for findReally common recurrencesShould know how to solve recurrences but also recognize somereally common ones:T(n) = O(1) + T(n-1) linearT(n) = O(1) + 2T(n/2) linearT(n) = O(1) + T(n/2) logarithmicT(n) = O(1) + 2T(n-1) exponentialT(n) = O(n) + T(n-1) quadratic (see previous lecture)T(n) = O(n) + T(n/2) linearT(n) = O(n) + 2T(n/2) O(n log n)Note big-Oh can also use more than one variable• Example: can sum all elements of an n-by-m matrix in O(nm)Spring 2010 14CSE332: Data AbstractionsAsymptotic notationAbout to show formal definition, which amounts to saying:1. Eliminate low-order terms2. Eliminate coefficientsExamples:–4n + 5–0.5n log n + 2n + 7– n3+ 2n+ 3n– n log (10n2)Spring 2010 15CSE332: Data AbstractionsBig-Oh relates functionsWe use O on a function f(n) (for example n2) to mean the set of functions with asymptotic behavior less than or equal to f(n)So (3n2+17) is in O(n2) –3n2+17 and n2 have the same