Efficiency Comparison: Analysis of MaxDistance and MaxDistance2

This report provides a comprehensive analysis of two algorithms, MaxDistance and MaxDistance2, designed to calculate the maximum distance between elements in a given list. The analysis includes a theoretical examination of their properties, correctness, and efficiency, as well as a practical comparison based on Java implementations. The algorithms are assessed in terms of time complexity, the number of basic operations performed, and actual execution time. The report details the implementation process, testing methodologies, and results obtained, offering insights into the strengths and weaknesses of each algorithm in various scenarios. Ultimately, the study aims to determine the more efficient algorithm based on empirical data and theoretical analysis, providing a clear understanding of their performance characteristics.

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

Analysis of Algorithms
 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.2.2 Elements
The working of algorithm MaxDistance2:
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.
Computation and Iteration: Few variables has been declared and defined for the computation
purposes of the algorithm which are dmax, temp, i and j. The three variables dmax, i and j have
been initialized with the value 0 while temp has only been declared and not initialized. 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. See below:
The first loop runs from 0 to ‘n-2’ positions and second loop runs from ‘i+1’ to ‘n-1’ positions.
This means that the outer loop will run for total ‘n-1’ iterations while inner loop will start
running first for ‘n-1’ iterations and with every increasing iteration of ‘i’, the number of times
the loop ‘j’ will run will be one less than the previous time, and for the last iteration of j the loop
will run only for one time. Hence for every iteration of ‘i’ the jth loop will run for (n-1)*(n-i-1)
times. For example:
When ‘i’ will be 0 it will be counted as:
i=0; Iteration 1:
j=1; iteration 1
8

Analysis of Algorithms
j=2; iteration 2
.
.
j=n-1; iteration n-1
Similarly for i=1
i=1; Iteration 2
j=2; iteration 1
j=3; iteration 2
.
.
j=n-1; iteration n-1
upto i=n-2, the last iteration for ‘i’ will be:
i=n-2; Iteration n-1
j=n-1; iteration 1
Terminate
Computations and evaluations inside inner loop:
Step 1: The value of variable ‘j’ will be initialized to ‘i+1’.
Step 2: The difference between the elements present at location A[i] and A[j] will be calculated.
The value of the difference will be stored in the variable ‘temp’. Now value of ‘temp’ will be
compared to the value of variable ‘dmax’, in case the value of ‘temp’ is greater than the value of
‘dmax’: the content of dmax will be changed by the value of temp i.e. dmax will now contain the
new value which will be equal to the current difference between A[i] and A[j]. In case the value
of ‘temp’ is smaller than ‘dmax’: the variable ‘j’ will be incremented by 1 automatically and step
9

Analysis of Algorithms
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-1’. The iteration will not be
calculated for ‘i=n-1’ and as soon the value of ‘i’ becomes equal to ‘n-1’ 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.
4. Describing Correctness of Algorithms
4.1 Partial Correctness
To prove the total correctness of an algorithm, we must prove that the algorithm returns an
output i.e. partial correctness of an algorithm and Termination of the algorithm (Cerny, Okseniuk
& Lawrence, 2013).
|- assert(P); C; assert(Q);
An algorithm is partially correct if the following statement can be proved true:
“If the pre-condition is true, the post-condition must be true”.
In the statement ‘|- assert(P); C; assert(Q);’
Assert(P) defines the pre-condition before the execution of the algorithm, C defines the
execution of the algorithm and Assert(Q) defines the post-condition before the execution of the
algorithm (Cerny et. al, 2013).
Pre-Condition: We have assumed that pre-condition for MaxDistance is initially satisfied i.e. The
array of integers A[1…n] hold only natural numbers between 1 and n such that 1<s<n; where s
and n are natural numbers. Also the value of dmax has been defined to be natural integer (Cerny
et. al, 2013).
dmax =0 and A[1---n] = 1<s<n
10

Analysis of Algorithms
Post-Condition: The variable dmax will contain the maximum distance between two of its
elements. To rule out the confusion of initial value of variable dmax and final value of dmax,
let’s denote the final value of dmax by dmax’.
dmax = either 0 or Maximum Distance
These pre-conditions and post-conditions remain same for both the algorithms.
4.1.1 Algorithm MaxDistance
Proof:
To prove the correctness of given algorithm:
i=0;j=0;dmax=0;
for (i<n;i++)
{
for (j<n;j++)
{
if (i==j) and (A[i]-A[j])>dmax
dmax= A[i]-A[j]);
} end for
}end for
return dmax
We can see that the major part of the algorithm contains a loop; hence if we prove that the loop
works in a correct manner and output is being produced, we can prove the partial correctness.
The following table shows the value of interest:
Iteration
Number
for outer
loop
(value of i)
0 1 2 3 -----
---
n-1
Iteration
Number
for inner
loop
(value of j)
0 1 2 n-1 0 1 2 n-1 0 1 2 n-
1
0 1 2 n-
1
-----
---
0 1 2 n
-
1
11