# Class 24: Algorithm Analysis (1)

Back to Project Discussion. On to Algorithm Analysis (2).

Held: Wednesday, 6 October 2004

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

Related Pages:

Assignments

Notes:

• Extra credit for attending convo tomrrow (in Harris).
• Today we pick groups.
• No more daily homework until after break. However, you have a project assignment due next Tuesday.

Overview:

• An Example.
• Comparing Algorithms.

## Motivating Problem: Exponentiation

• Consider the problem of computing xy for double x and positive integer y.
• How do we do it?
• Simple iterative solution: a for loop.
```double result = 1.0;
for (int i = 0; i < y; i++)
result *= x;
```
• This algorithm is fairly slow. Can we do better?
• We might try using a standard algorithm design practice: divide and conquer
• Split the problem "in half"
• Solve one or both halves
• Combine the solutions
• You should have seen this idea in binary search and merge sort (or quick sort)
• What can we divide in half? The exponent (provided it's even)
```To compute x^y
If y is 0
return 1
Else if y is odd
return x*x^(y-1)
Else if y is even
return square(x^(y/2))
```

## 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 xy, one might use repeated multiplication, divide and conquer, or even the built-in en and natural log procedures.
• 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.

Back to Project Discussion. On to Algorithm Analysis (2).

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Wed Dec 8 10:37:17 2004.
The source to the document was last modified on Thu Aug 26 20:22:23 2004.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2004F/Outlines/outline.24.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu