Algorithms - Analysis of Algorithms

Analysis of Algorithms

There are 2 ways of doing this:

• Inspecting pseudo code.  This is the analytical approach


• Implement the algorithm and time it. This is the experimental approach

The analytical approach is usually preferred because:

• Not affected by programming


• Not affected by the computer used


• Gives a proof of the running time for inputs of any value of n

Primitive Operations

To inspect pseudo code we count the primitive operations, for example the number of:

• Memory accesses


• Arithmetic operations


• Comparisons

All these operations should be O(1), meaning they are of a constant time.

The Recipe for Analysis

1. Preheat your oven to 180 degrees / Gas mark 5


2. Get the pseudo code


3. Find the main operations


4. Identify the worst case input


5. Count the operations


6. Write down the equation t(n) = ...


7. Simplify using Big O


8. Ignore step 1

There's a good example in the notes but it's quite difficult to copy it out to here, but see pages 8 - 12 of this for it.

Experimental Analysis

You might want to know how long an algorithm will take on a specific piece of hardware, or it might be difficult to inspect the code. This would be a good time to do an experimental analysis.

The Experimental Recipe

1. Implement the algorithm


2. Run it for a range of input sizes


3. Make repeated measurements of run time


4. Plot results of time against n, fit to a line


5. Extrapolate if needed


6. Estimate big O

Reading from a log plot

When you need to measure the gradient of a line on a log plot, make sure you do not take the numbers literally and instead use the exponents (see page 27). Make sure you read the actual number though for the gradient.

That's the end. Again, these notes are really short because they are really just the key points from the lectures, but you definitely need to look at the examples and the text book too!