Notes on Session A3: Analyzing Algorithms

Experiment A3.1, Step 1. You will likely have seen a variety of different running times, but hopefully without much difference. Why? Because a number of external factors can influence the wall-clock time. Some of those factors are covered in the preceding discussion.

Experiment A3.1, Step 6. You will likely see much longer times and much more variation in times. Why? Because you are timing not just the algorithm, but also the time it took you to write the input. Humans are often much slower and much more variable than computers.

Experiment A3.1, Step 7. The first call to fib likely took significantly longer than the others. Why? Because Java needs to do a number of things the first time a method is invoked (e.g., on some machines a just-in-time compiler will convert the Java virtual machine code to local machine code). For subsequent calls to the method, that work does not need to be done.

Experiment A3.3, Step 3. You may have noted that the number of steps was different each time. Why? Because we neglected to reset the counter each time through the loop.

Experiment A3.6, Step 5. If you only count the number of times the body in the loop is executed, the number of steps in smallest is likely one less than the number of elements in the sequence.