CS151 lecture notes, Fall 1999 Week 14, Monday Analysis of algorithms ---------------------- Analysis of algorithms is an area of computer science on the border between CS and mathematics. It uses many of the tools of mathematics 1) abstract algebra 2) proof techniques But it has a very practical aspect -- the design and analysis of fast algorithms. By now you should have an idea what an algorithm is. Analysis of bisection search ---------------------------- How many comparisons do you have to do in a linear search? One for each element of the array. If array size is n, there are n comparisons. How many comparisons do you have to do in a bisection search? (Don't forget that the array has to be sorted. Can we prove that you can't search an unsorted array in fewer than n comparisons?) One each time we divide the array in half. How many times can we divide the array (size n) before we get to one? How many times do we have to double 1 before we get to n? What power of 2 is n? What mathematical function answers that question? Logarithm! The amount of work in a bisection search is proportional to the logarithm of the number of elements in the (sorted) array. What is the base of the logarithm? In this case, 2, but in general it doesn't matter much. We are more interested in the order of growth than the exact run time. Order of Growth --------------- Often it is useful to characterize how a function behaves as n gets large. Remember what n is -- it's the number of things getting searched, or sorted, or whatever. It's the "problem size". We are mostly interested in large values of n because when n is small, any algorithm will be fast enough. As n gets big, the choice of algorithm becomes more important. How different are n and log n? n log n - ----- 10 1 100 2 1000 3 10000 4 Clearly n is getting big much faster than log n. What if the log n term is multiplied by a constant factor? Very often, it doesn't matter, because there will still be a value of n where (1000 log n) is less than n, no matter what the leading constant is. Analysis of Mergesort --------------------- How many comparisons do you have to do using the simple sort algorithm? Have to traverse the array (n iterations). At each iteration we have to find the largest among n-i elements (where i is the iteration number). Total comparisons = n + (n-1) + (n-2) + ... + 1 Draw a triangle diagram to motivate the solution n/2 (n-1) The leading order term is n^2, which means that as n gets big, the behavior of this curve is like n^2. How many comparisons do you have to do in a mergesort? At each level of recursion, the number of comparisons is n-1. How many levels of recursion are there? Object methods -------------- Observation: lots of methods operate on a single object that is passed on a parameter. The object-oriented view of this is that you are invoking a method "on" an object, or sometimes people say you are passing a message to the object. Either way, there is the notion that one of the parameters is special. OBJECT METHODS are an alternate syntax that makes the special parameter invisible! Object methods we have seen: g.drawOval (...); string.charAt (1); When you invoke them, you invoke them "on" an object. All the methods we have written have been CLASS METHODS. You just invoke them. Possible confusion: Sometimes when you invoke a CLASS METHOD, you specify the name of the class, as in Card.printCard (...); Math.cos (...); How can we tell when we are invoking a CLASS or OBJECT method? Ok, so how do we WRITE object methods? 1) leave out the word static! 2) leave out the magic parameter In that case, how do we refer to the magic parameter? 1) using the keyword this OR 2) implicitly! Examples: printDeck and printCard plenty more examples in Chapter 13!