Comparison of Two Algorithms for Maximum Distance Calculation

Analysis of Algorithms
Comparison of Two Algorithms

Analysis of Algorithms
Table of Contents
1. Abstract........................................................................................................................................3
2. Introduction..................................................................................................................................3
3. Describing Algorithms.................................................................................................................4
3.1 Algorithm 1: MaxDistance....................................................................................................4
3.1.1 Properties........................................................................................................................4
3.1.2 Elements.........................................................................................................................5
3.2 Algorithm 2: MaxDistance2..................................................................................................7
3.2.1 Properties........................................................................................................................7
3.2.2 Elements.........................................................................................................................7
4. Describing Correctness of Algorithms......................................................................................10
4.1 Partial Correctness...............................................................................................................10
4.1.1 Algorithm MaxDistance...............................................................................................10
4.1.2 Algorithm MaxDistance2.............................................................................................12
4.2 Termination..........................................................................................................................13
5. Comparison of MaxDistance and MaxDistance2 on basis of Efficiency..................................14
5.1. Measure problem size for the algorithm.............................................................................14
5.2. Measure running time using count of basic operations......................................................15
5.2.1 Time Complexity of MaxDistance...............................................................................15
5.2.2 Time Complexity of MaxDistance2.............................................................................16
5.3 Determine worst-case, best-case and average case efficiency.............................................16
6. Implementation and Testing of Algorithms...............................................................................19
6.1 Programming Language and Environment..........................................................................19
6.2 Algorithm Implementation in Java......................................................................................20
6.2.1 Java Implementation of MaxDistance..........................................................................20
1

Analysis of Algorithms
6.2.2 Java Implementation of MaxDistance2........................................................................22
6.3 Program Testing...................................................................................................................23
6.4 Test Data..............................................................................................................................24
6.5 Measure Basic Operations Count........................................................................................25
6.6 Measure Execution Time.....................................................................................................26
7. Implementation Results.............................................................................................................26
7.1 Results that shows the correctness of the program..............................................................26
7.2 Results of comparing the number of Basic Operations.......................................................29
7.3 Results of comparing execution times.................................................................................32
References:....................................................................................................................................38
Appendix:......................................................................................................................................40
2

Analysis of Algorithms
1. Abstract
This report discusses the analysis of the two given algorithms, comparison between them on the
basis of efficiency and correctness, in both theoretical and practical manner. To analyze these
algorithms, both have been implemented using Java and their runtime characteristics has been
measured and compared based on count of the number of total operations performed by the
algorithms and total execution time taken by each of them.
2. Introduction
In Analysis of algorithms we study and compare two or more algorithms under some specified
circumstances which remains same for all and their results are measured on the basis of their
space and run time requirements (Almuallim & Dietterich, 2014). The reason why analyze the
algorithms is, to discover the most suitable algorithms for a particular application depending on
its environment. To analyze the execution time of an algorithm the procedure that has to be
followed is:
 Implementation of all algorithms using same language.
 Evaluate the time taken to perform all the basic operations
 Discover unidentified quantities which can help to define basic operations’ execution
frequency.
 As an input to the program develop a realistic model.
 Assuming the modeled input, examine the unknown quantities.
 Evaluate the total execution time: multiply frequency by time and add.
To calculate the theoretical time efficiency of the two algorithms, Average-Case Analysis has
been performed on both of them i.e. both algorithms have been tested over all possible inputs. To
test the efficiency, the algorithms have been implemented in JAVA language using all its data
sets and structure alignment. Similar basic operations and problem size have been applied to both
to compare the results and predict the efficiency. A proper approach has been followed to
develop test data and chose cases under different input sizes (Almuallim & Dietterich, 2014).
3

Analysis of Algorithms
The last section of this report describes the outcome of the analysis and defines the best and
worst algorithm, the basis of the outcome has been counted as ‘number of basic operations’ and
‘execution time’ i.e. space and time requirements.
3. Describing Algorithms
The two algorithms provided for the comparison and analysis purpose performs the same
function i.e. to calculate the maximum distance between two of its elements. For example,
suppose there are five random numbers 12, 34, 40, 1 and 6, the algorithm will calculate the
difference between every pair of numbers like (12 and 34), (12 and 40), (12 and 1), (12 and 6),
(34 and 40) and so on (Almuallim & Dietterich, 2014). Every time a greater difference is found
between two variables, the value of the return variable will be altered with the greater difference
and after the loop ends the maximum difference possible will be returned. In this case the output
that will be returned is 39 as the maximum difference between its two elements, which is the
difference between 1 and 40. No other pair will have greater difference than this (Biebricher,
Fuhr, Lustig, Schwantner & Knorz, 2016).
Let’s understand both algorithms in a more clear and understandable manner with the help of
algorithm properties and elements.
3.1 Algorithm 1: MaxDistance
The algorithm MaxDistance has been designed to generate the maximum distance between two
of the elements that has been provided as input. It has following properties.
3.1.1 Properties
 Finiteness: Algorithm MaxDistance has a finite number of steps and instructions and it
will surely terminate after completion of all steps. This algorithm does not have any
infinite loop running in it (Balcom, Laura & Tong, 2015).
 Definiteness: Every instruction in the algorithm MaxDistance has been defined precisely
and in a very clear manner which can be understood with very little efforts. No step or
instruction has any kind of ambiguity.
Example:
4

Analysis of Algorithms
The above lines have been copied from the given algorithm which clearly shows that
input and output statements have been defined in such manners which are self-
explanatory (Balcom et. al, 2015).
 Input: The algorithm MaxDistance takes a list of integer numbers as input which is
entered by the user during run time. These numbers are finite and can either be defined in
the source code or can be asked from the user during run time. These numbers will then
be stored as an array of integers (Balcom et. al, 2015).
 Output: The algorithm returns one single output that is the maximum distance between
two of the elements provided in the input section as the list of integers (Balcom et. al,
2015).
3.1.2 Elements
The working of algorithm MaxDistance:
Acquire Data (Input): During run time the user will be prompted to enter ‘n’ numbers. This ‘n’
can either be defined explicitly within the source code with some finite digit or can be asked
from the user while executing. Depending upon the size allowed an integer array A[] has been
declared that can store that many numbers. When user is prompted to enter ‘n’ numbers, it is
expected from the user to input a list of integer elements only otherwise run time error will be
accounted (Biebricher, et. al, 2016).
Computation and Iteration: Few variables has been declared and defined for the computation
purposes of the algorithm which are dmax, i and j. All three variables have been initialized with
the value 0. There are two iterations in this algorithm one of them runs as the outer loop which is
controlled by the ‘i’ variable and another runs as the inner loop which is controlled by the ‘j
variable (Biebricher, et. al, 2016). See below:
5

Analysis of Algorithms
The first loop runs from 0 to ‘n-1’ positions and second loop also runs from ‘0’ to ‘n-1’
positions. This means that there will be total ‘n’ iterations for the outer loop where inside each
iteration of the outer loop there will be ‘n’ iterations. So there will be total ‘n * n’ iterations. For
example:
When ‘i’ will be 0 it will be counted as:
i=0; Iteration 1:
j=0; iteration 1
j=1; iteration 2
.
.
j=n-1; iteration n
Similarly for i=1
i=1; Iteration 2
j=0; iteration 1
j=1; iteration 2
.
.
j=n-1; iteration n
upto i=n-1
Computations and evaluations inside inner loop:
For each iteration of variable ‘i’ these steps will be performed:
Step 1: The value of ‘j’ will be initialized to zero
6

Analysis of Algorithms
Step 2: The value of ‘i’ and ‘j’ will be compared and if they are equal, the inner loop will break
at that very point; next iteration of ‘j’ will be computed. In case variable ‘i’ and variable ‘j’ are
not equal difference will be calculated between A[i] and A[j] and if the difference comes out to
be greater than the value of dmax, the value of dmax will be replaced by the difference of A[i]
and A[j]. The value of the variable ‘j’ would be incremented automatically by 1 and step 2 will
be repeated until value of ‘j’ reaches ‘n-1’. After the value of ‘j’ becomes equal to ‘n’, the
counter will move to step 1.
The outer loop will terminate after variable ‘i’ reaches value ‘n’. The iteration will not be
calculated for ‘i=n’ and as soon the value of ‘i’ becomes equal to ‘n’ it will come out of the outer
loop.
Report Results: The final value of the variable ‘dmax’ which has been computed in the
processing steps will be returned and displayed to the user. This value will represent the
maximum distance between two of its elements.
3.2 Algorithm 2: MaxDistance2
The algorithm MaxDistance2 has the same function as that of MaxDistance been i.e. to generate
the maximum distance between two of the elements that has been provided as input. It has
similar properties as that of MaxDistance.
3.2.1 Properties
 Finiteness: Algorithm MaxDistance2 has a finite number of steps and instructions and it
will surely terminate after completion of all steps. This algorithm does not have any
infinite loop running in it (Balcom et. al, 2015).
 Definiteness: Every instruction in the algorithm MaxDistance2 has been defined
precisely and in a very clear manner which can be understood with very little efforts. No
step or instruction has any kind of ambiguity (Balcom et. al, 2015).
 Input: The algorithm MaxDistance2 takes a list of integer numbers as input which is
entered by the user during run time. These numbers are finite and can either be defined in
the source code or can be asked from the user during run time. These numbers will then
be stored as an array of integers (Balcom et. al, 2015).
7