Class 33: Algorithm Analysis (1)

Held: Friday, 28 October 2005

Summary: Today we consider techniques for comparatively evaluating the running time of algorithms.

Related Pages:

• EBoard.

Overview:

• Comparing algorithms.
• Difficulties.
• Informal analysis.
• Experimental analysis.

Comparing Algorithms

• As you may have noted, there are often multiple algorithms one can use to solve the same problem.
  • In finding the minimum element of a list, you can step through the list, keeping track of the current minimum. You could also sort the list and grab the first element.
  • In finding x^y, one might use repeated multiplication, divide and conquer, or even the built-in eⁿ and natural log procedures.
  • In computing the nth Fibonacci number, you can recurse according to the formula or use a Vector to cache previously computed results.
  • In destructively counting values in a Vector equal to a specified value, you can start at the left or start at the right.
  • In searching a Vector for a value, you can use sequential search, binary search, or random probing.
  • You can come up with your own variants.
• How do we choose which algorithm is the best?
  • The fastest/most efficient algorithm.
  • The one that uses the fewest resources.
  • The clearest.
  • The shortest.
  • The easiest to write.
  • The most general.
  • ...
• Frequently, we look at the speed. That is, we consider how long the algorithm takes to run.
  • It is therefore important for us to be able to analyze the running time of our algorithms.

Difficulties Analyzing Running Times

• Is there an exact number we can provide for the running time of an algorithm?
  • Surprisingly, no.
• Different inputs lead to different running times. For example, if there are conditionals in the algorithm (as there are in many algorithms), different instructions will be executed depending on the input.
• Not all operations take the same time. For example, addition is typically quicker than multiplication, and integer addition is typically quicker than floating point addition.
• The same operation make take different times on different machines.
• The same operation may appear to take different times on the same machine, particularly if other things are happening on the same machine.
• Many things that affect running time happen behind the scenes and cannot be easily predicted. For example, the computer might move some frequently-used data to cache memory.
• We therefore model the likely shape of the curve of running time vs. input size.
• We will build these models both by static analysis of the program code and experimentally (running the code on a variety of sizes of inputs).
  • We hope that the two forms match each other.

Informal Analysis

• A good starting point is to informally determine the time vs. input size curve for the algorithm.
• Because the same input size can have different running times, we usually start by bounding above. (What's the worst that can happen.)
  • Sometimes we also look at a best case and bound below.
  • If we're lucky, the upper and lower bounds are the same. They rarely are.
• For iterative algorithms, it's often best to count the steps in an algorithm and then add them up.
  • Assume most things take one step.
  • If you call a function, you'll need to analyze the running time of that function
  • For loops, analyze the body of the loop and then multiply by the number of times the loop repeates.
  • For conditionals, analyze the two halves of the conditional and take the largest.
• We may find other ways to count, too.
• Since it is difficult to speak to the relationship between different basic operations, we usually eliminate constant multiplers.

Experimental Analysis

• Particularly as you start to analyze algorithms, it may be helpful to analyze them experimentally as well as abstractly.
• What do I mean when I say analyze them experimentally? I mean that we can time them on a variety of inputs and graph the results.
• If the experimental and the abstract results match, we can be fairly confident in the abstract results.
• If they don't, we may need to reflect and try again.
  • Our analysis may be correct and our implementation incorrect.
  • Our analysis may be correct and our data may all be outliers.
  • Our analysis may be incorrect.
  • ...
• Note that some analyses can be very difficult.