INN701 Lecture 1
CRICOS No. 00213J
a university for the worldreal R
Empirical analysis of algorithms
• After confirming the acceptability of an algorithm’s efficiency
theoretically, we may still want to analyse its behaviour
experimentally in its intended computing environment
– The actual program may not perform as well as predicted due to
memory management overheads, preemption by concurrent
processes, etc
– On rare occasions the program may perform better than
expected thanks to compiler optimisations, e.g., hoisting code
out of loops
1
CRICOS No. 00213J
a university for the worldreal R
Procedure for empirical analysis of the
efficiency of an algorithm
1. Understand the experiment’s purpose.
2. Decide on the efficiency metric to be measured and the
measurement unit (an operation count vs. a time unit).
3. Decide on characteristics of the input sample (its range, size, and
so on).
4. Prepare a program implementing the algorithm (or algorithms) for
the experimentation.
5. Generate a sample of inputs.
6. Run the algorithm(s) on the sample’s inputs and record the data
observed.
7. Analyze the data obtained
2
CRICOS No. 00213J
a university for the worldreal R
Step 1: Understand the experiment’s purpose
• Different goals one can purse in analysing algorithm(s) empirically:
– To check the accuracy of a theoretical assertion about the
algorithm’s efficiency
– To compare the efficiency of several algorithms for solving the
same problem
– To compare different implementations of the same algorithm
– To develop a hypothesis about the algorithm’s efficiency class
– To ascertain the efficiency of the program implementing the
algorithm on a particular machine
• An experiment’s design depends on the experiment’s purpose
3
CRICOS No. 00213J
a university for the worldreal R
Step 2: Decide on the efficiency metric to be
measured and measurement unit
• Two common efficiency metrics:
– The number of times the algorithm’s basic operation is executed
– The execution time of the algorithm’s implementation
4
CRICOS No. 00213J
a university for the worldreal R
Step 3: Decide on characteristics of input
sample
• Determine the problem size parameter(s)
• Identify a basic operation and all the instances of the basic operation
5
CRICOS No. 00213J
a university for the worldreal R
Step 4: Prepare a program implementing the
algorithm (or algorithms) for the
experimentation
• Choose a programming language, and use it to implement the algorithm
• Test the program to make sure the behaviours of the algorithm are not
changed
• The program for counting the number of times the basic operation is
performed and the program for testing the execution time of the program
should be separated
• The program for the number of times the algorithm’s basic operation is
executed
– Insert a counter to count the number of times the algorithm’s basic
operation is executed
• Make sure the counter is inserted at a correct place
• Make sure all the instances of the basic operation will be counted
6
CRICOS No. 00213J
a university for the worldreal R
Step 4: Prepare a program implementing the
algorithm (or algorithms) for the
experimentation – cont.
• The program for testing the execution time of the algorithm
– Record the system time right before the program implementation
starts to run
– Record the system time right after the program implementation
finishes to run
– Calculate the difference between the two to get the execution
time of the program
7
CRICOS No. 00213J
a university for the worldreal R
Step 4: Prepare a program implementing the
algorithm (or algorithms) for the
experimentation – cont.
• A system’s time is typically not accurate and you might get different
results on repeated runs of the same program
– To repeatedly run the program multiple times and then take the
average of the multiple runs of the program
• The running time may fail to register at all and be reported as zero
– To run the program in a loop, measure the total running time,
and then divide it by the number of the loop’s repetitions
8
CRICOS No. 00213J
a university for the worldreal R
Step 5: Generate a sample of inputs
• Whether you decide to measure the efficiency by basic operation
counting or by time clocking, you will need to decide on a sample of
inputs for the experiment.
• If there are benchmarks available, then you may use the
benchmarks
• If there is no benchmark, then you have to make decisions about the
range of input sizes, the sizes of sample inputs, number of times
each case needs to be repeated.
• You may need to develop a program to randomly generate a sample
of inputs
9
CRICOS No. 00213J
a university for the worldreal R
Step 6: Run the algorithm(s) on the sample’s
inputs and record the data observed
• Run the algorithm implementation for the sample of input and record
the data observed
• Calculate the average number of times and/or the average
execution time for each input size, if we need to run multiple times
for the input size
10
CRICOS No. 00213J
a university for the worldreal R
Step 7: Analyze the data observed
• The data observed need to be analysed
• In order to analyse the data observed, we need to present them
– Data can be presented numerically in a table or graphically in a
scatterplot
– It is a good idea to present the data observed in both the
methods as each has its strengths and weaknesses
– In a tabular presentation, it is easy to manipulate the data
• For example, it is easy to calculate the ratios t(n)/g(n) and
t(2n)/t(n), where t(n) is the number of times the basic
operation was performed or the actual execution time and
g(n) is a candidate efficiency class
– In a scatterplot presentation, it is easy to assert the algorithm’s
efficiency class
11
CRICOS No. 00213J
a university for the worldreal R
Step 7: Analyze the data observed
12
(10000) 140538
2.089
(5000) 67272
(8000) 113063
2.133
(4000) 53010
t
t
t
t
= =
= =
Since the ratio of t(2n) and t(n) is greater than 2,
the algorithm is less efficient than O(n); since the
ratio is less than 4, the algorithm is more efficient
than O(n2). Thus, the efficiency class of the
algorithm is between O(n) and O(n2). O(n log n) is
such an efficiency class.
By checking against the experimental results, we
can confirm that the efficiency class of the
algorithm is O(n log n).
Hypothesize a likely efficiency class of an algorithm based on the following
empirical observations of its basic operation’s count:
(2 ) (2 )log(2 ) 2log(2 )
( ) log log
t n n n n
t n n n n
= =
Empirical analysis of algorithms
Procedure for empirical analysis of the efficiency of an algorithm
Step 1: Understand the experiment’s purpose
Step 2: Decide on the efficiency metric to be measured and measurement unit
Step 3: Decide on characteristics of input sample
Step 4: Prepare a program implementing the algorithm (or algorithms) for the experimentation
Step 4: Prepare a program implementing the algorithm (or algorithms) for the experimentation – cont.
Step 4: Prepare a program implementing the algorithm (or algorithms) for the experimentation – cont.
Step 5: Generate a sample of inputs
Step 6: Run the algorithm(s) on the sample’s inputs and record the data observed
Step 7: Analyze the data observed
Step 7: Analyze the data observed