Homework 2 Clarifications

• Problem #2 (Weiss 2.1) For this question in general, the main thing you need to do is to be able to compare two functions to see which one grows faster. A couple of techniques that are useful in this respect are things like taking the log of both sides, or treating both sides as exponents when the base is something that leads to further simplification. We are talking about "growth rate", thus another way of thinking about these is saying find their running time in terms of big O, and then order them by that.
• Problem #4 (Weiss 2.7) The idea of part c is that we talked about how big-O was useful for comparing the run time of two algorithms. And we said that in fact we could do a big-O analysis and then use THAT to decide which algorithm to use. (as opposed to implementing the algorithms and then running them and timing them and seeing which was faster). Well in this case we are asking you to do both! So you can actually see what the running time is if you DO implement and time them.