Homework 2 Clarifications

• Problem #2 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. Do be careful if you use technique like taking the log or treating both sides as exponents to realize that rules like discarding coefficients don't necessarily apply after you have made a transformation like that however.


• Problem #4: I have had a few people asking questions about whether they are seeing what they should be seeing in their timing. Here are a few pointers:
  • Be sure that you have your code correct: In between the two calls to System.nanoTime() you should only have the code that is one of the loop bodies. Double check that you copied the code correctly, that you have an n when you should and an i when you should - these make a big difference in the running time.
  • Run each loop several times: For each value of n that you try, for each of the pieces of code you are trying, run it 3-4 times or more. One thing you can do is to throw out the smallest and the largest time you get and take an average of the remaining ones.
  • Values for n: Be sure that you run each piece of code for at least 4 different values of n. You do not have to use the exact same values of n for each of the 5 pieces of code. For some pieces of code you may not want to wait for it to finish for any value of n > 1000 (which is not actually a very large value of n). For other pieces of code you will want to run for larger values in order to see the trend for large n.
  • Should my timing values map exactly (or even approximately?) to a curve of some function of N? Shouldn't this be identical to what I predicted the big-O running time to be? What if it isn't? Don't worry if the timings you get don't match exactly what you think they should be based on your big-O analysis. Hopefully you will see that if you had based your choice of algorithm on big-O you still would have made the right choice in terms of observed running times (e.g. that one piece of code runs slower than another for large values of N as big-O would have predicted). NOT nescessarily that the observed running times of one piece of code exactly match a curve of the big-O function you think represents that code. Look for relative trends.
  • I did everything you mention above but I still get crazy values I don't understand. To some extent your answers will depend on your machine. You may have multiple cores or only one. You may have some other process running on your machine that is causing your code to run more slowly (I would try to close other active programs while timing.). In the end just be sure you have followed all the instructions in the assignment, reported timing for at least 4 values of n for each piece of code and have said *something* about what you saw in your results even if they did not make complete sense to you.