ASSIGNMENT 1: Algorithm Complexity Analysis

BBM204 Software Laboratory II
PROGRAMMING ASSIGNMENT 1
Subject: Algorithm Complexity Analysis
1 Introduction
Analysis of algorithms is the area of computer science that provides tools to analyze the
efficiency of different methods of solutions. Efficiency of an algorithm depends on these
parameters; i) how much time, ii) memory space, iii) disk space it requires. Analysis of
algorithms is mainly used to predict performance and compare algorithms that are developed
for the same task. Also it provides guarantees for performance and helps to understand
theoretical basis.
A complete analysis of the running time of an algorithm involves the following steps:
• Implement the algorithm completely.
• Determine the time required for each basic operation.
• Identify unknown quantities that can be used to describe the frequency of execution of
the basic operations.
• Develop a realistic model for the input to the program.
• Analyze the unknown quantities, assuming the modeled input.
• Calculate the total running time by multiplying the time by the frequency for each
operation, then adding all the products.
BBM204 Programming Assignment 1 1
Spring 2023
BBM204 Software Laboratory II
ò
In this experiment, you will analyze different sorting and searching algorithms
and compare their running times on a number of inputs with changing sizes.
2 Background and Problem Definition
Efficient sorting is important for optimizing the efficiency of other algorithms (such as search
and merge algorithms) that require input data to be sorted. Furthermore, modern computing
and the internet have made accessible a vast amount of information. The ability to efficiently
search through this information is fundamental to computation. The efficiency of a sorting
algorithm can be observed by applying it to sort datasets of varying sizes and other characteristics of the dataset instances that are to be sorted. In this assignment, you will be classifying
the given sorting and searching algorithms based on two criteria:
• Computational (Time) Complexity: Determining the best, worst and average case
behavior in terms of the size of the dataset. Table 1 illustrates a comparison of computational complexity of some well-known sorting and searching algorithms.
Table 1: Computational complexity comparison of some well-known algorithms.
Algorithm Best Case Average Case Worst Case
Bubble Sort Ω(n) Θ(n
2
) O(n
2
)
Insertion Sort Ω(n) Θ(n
2
) O(n
2
)
Heap Sort Ω(n log n) Θ(n log n) O(n log n)
Quick Sort Ω(n log n) Θ(n log n) O(n
2
)
Merge Sort Ω(n log n) Θ(n log n) O(n log n)
Radix Sort Ω(nk) Θ(nk) O(nk)
Linear Search Ω(1) Θ(n) O(n)
Binary Search Ω(1) Θ(log n) O(log n)
• Auxiliary Memory (Space) Complexity: Some sorting algorithms are performed
“in-place” using swapping. An in-place sort needs only O(1) auxiliary memory apart
from the memory used for the items being sorted. On the other hand, some algorithms
may need O(log n) or O(n) auxiliary memory for sorting operations. Searching algorithms usually do not require additional memory space. Table 2 illustrates an auxiliary
space complexity comparison of the same well-known sorting and searching algorithms.
Table 2: Auxiliary space complexity comparison of some well-known algorithms.
Algorithm Auxiliary Space
Complexity
Bubble Sort O(1)
Insertion Sort O(1)
Heap Sort O(1)
Quick Sort O(log n)
Merge Sort O(n)
Radix Sort O(k + n)
Linear Search O(1)
Binary Search O(1)
BBM204 Programming Assignment 1 2
Spring 2023
BBM204 Software Laboratory II
A time complexity analysis focuses on gross differences in the efficiency of algorithms that
are likely to dominate the overall cost of a solution. See the example given below:
Code Unit Cost Times
i=1; c1 1
sum = 0; c2 1
while (i ≤ n) { c3 n + 1
j=1; c4 n
while (j ≤ n) { c5 n · (n + 1)
sum = sum + i; c6 n · n
j = j + 1; c7 n · n
}
i = i +1; c8 n
}
The total cost of the given algorithm is c1 + c2 + (n + 1) · c3 + n · c4 + n · (n + 1) · c5 + n ·
n · c6 + n · n · c7 + n · c8. The running time required for this algorithm is proportional to n
2
,
which is determined as its growth rate, and it is usually denoted as O(n
2
).
3 Assignment Tasks
The main objective of this assignment is to show the relationship between the
running time of the algorithm implementations with their theoretical asymptotic
complexities. You are expected to implement the algorithms given as pseudocodes, and
perform a set of experiments on the given datasets to show that the empirical data follows
the corresponding asymptotic growth functions. To do so, you will have to consider how to
reduce the noise in your running time measurements, and plot the results to demonstrate and
analyze the asymptotic complexities.
3.1 Sorting Algorithms to Implement
You are given three different sorting algorithms to implement in this assignment. The sorting
should be implemented in ascending order.
• Comparison based sorting algorithms: In comparison-based sorting algorithms,
the elements are compared to determine their order in the final sorted output. You will
implement the following two comparison based sorting algorithms:
– Selection sort given in Alg. 1
– Quick sort (iterative implementation) given in Alg. 2
• Non-comparison based sorting algorithms: There are sorting algorithms that can
run faster than O(n log n) time complexity, but they require special assumptions about
the input sequence to determine the sorted order of the elements. Non-comparison based
sorting algorithms use operations other than comparisons to determine the sorted order
and may perform in O(n) time complexity. You will implement the following noncomparison based sorting algorithm:
– Bucket sort given in Alg. 3
BBM204 Programming Assignment 1 3
Spring 2023
BBM204 Software Laboratory II
Algorithm 1 Selection Sort
1: procedure SELECTION-SORT(list: array of items, n: size of list)
2: for i from 1 to n - 1 do
3: min ← i
4: for j from i+1 to n do
5: if list[j] < list[min] then
6: min ← j
7: end if
8: end for
9: if min ̸= i then
10: swap list[min] and list[i]
11: end if
12: end for
13: end procedure
Algorithm 2 Quick Sort (iterative implementation)
1: procedure QUICK-SORT(array : list of sortable items, low : first element of list, high : last element of
list)
2: stackSize ← high - low + 1
3: stack ← [ ] of length stackSize
4: top ← -1
5: stack[++top] ← low
6: stack[++top] ← high
7: while top ≥ 0 do
8: high ← stack[top - -]
9: low ← stack[top - -]
10: pivot ← partition(arr, low, high)
11: if pivot - 1 > low then
12: stack[++top] ← low
13: stack[++top] ← pivot - 1
14: end if
15: if pivot + 1 < high then
16: stack[++top] ← pivot + 1
17: stack[++top] ← high
18: end if
19: end while
20: end procedure
21: procedure PARTITION(array : list of sortable items, low : first element of list, high : last element of
list)
22: pivot ← arr[high]
23: i ← low - 1
24: for j from low to high do
25: if arr[j] ≤ pivot then
26: i ← i + 1
27: swap arr[i] with arr[j]
28: end if
29: end for
30: swap arr[i+1] and arr[high]
31: return i + 1
32: end procedure
BBM204 Programming Assignment 1 4
Spring 2023
BBM204 Software Laboratory II
Algorithm 3 Bucket Sort
1: procedure BUCKET-SORT(A: array, n)
2: numberOfBuckets ←
p
len(A)
3: buckets ← an array of empty arrays with the length numberOfBuckets
4: max ← max(A)
5: for each i in A do
6: Append i to buckets[hash(i, max, numberOfBuckets)]
7: end for
8: Sort each bucket individually
9: sortedArray ← [ ]
10: for each bucket in buckets do
11: Add all elements of the bucket to sortedArray
12: end for
13: return sortedArray
14: end procedure
15: procedure HASH(i, max, numberOfBuckets)
16: return ⌊i/max × (numberOfBuckets − 1)⌋
17: end procedure
3.2 Search Algorithms to Implement
You are given two different search algorithms to implement in this assignment.
• Linear Search given in Alg. 4
• Binary Search given in Alg. 5
Algorithm 4 Linear Search
1: procedure LINEAR-SEARCH(A: array to search in, x: value to be searched)
2: size ← len(A)
3: for each i ← 0 to size - 1 do
4: if A[i] == x then
5: return i
6: end if
7: end for
8: return -1
9: end procedure
Algorithm 5 Binary Search
1: procedure BINARY-SEARCH(A: sorted array, x: value to be searched)
2: low ← 0
3: high ← len(A - 1)
4: while high - low > 1 do
5: mid ← (high + low) / 2
6: if A[mid] < x then
7: low ← mid + 1
8: else
9: high ← mid
10: end if
11: end while
12: if A[low] == x then
13: return low
14: else if A[high] == x then
15: return high
16: end if
17: return -1
18: end procedure
BBM204 Programming Assignment 1 5
Spring 2023
BBM204 Software Laboratory II
3.3 Dataset
You will test the given sorting algorithms on a shortened version of a real dataset that
contains a great amount of recorded traffic flows of a test network, generated from a real
network trace through FlowMeter. This dataset (TrafficFlowDataset.csv) includes more than
250,000 captures of communication packets (e.g., header, payload, etc.) sent in a bidirectional
manner between senders and receivers over a certain period of time. FlowMeter generates
more than 80 record features including Flow ID, source and destionation IPs, etc. As it is
out of the scope of this assignment, you do not need to know the details about the type of
information recorded in these features, so do not get confused by them.
In order to be able to perform a comparative analysis of the performance of the given sorting
algorithms over different data sizes, you will consider several smaller partitions of the dataset,
that is, its subsets of sizes 500, 1000, 2000, 4000, 8000, 16000, 32000, 64000, 128000, and
250000 starting from the beginning of the file. You will be sorting and searching in the
records based on the Flow Duration feature given in the 7th column (Flow Duration),
which is of type int (see Fig. 1).
Figure 1: Sorting and searching in the data in the Flow Duration column only.
3.4 Experiments and Analysis Tasks
ò
Assignment Steps Summarized:
• Implement the given algorithms in Java.
• Perform the experiments on the given datasets.
– Tests with varying input sizes.
– Tests on random, sorted, and reversely sorted inputs.
• Fill out the results tables and plot the results.
• Discuss the findings.
Once you have implemented the given algorithms in Java, you need to perform a set of
experiments, report, illustrate, and analyze the results, and discuss your findings.
BBM204 Programming Assignment 1 6
Spring 2023
BBM204 Software Laboratory II
3.4.1 Experiments with Sorting Algorithms
In this set of experiments, you will run the given sorting algorithms on different input types
and sizes.
Experiments on the Given Random Data In the first set of experiments, you will
test the algorithms on the given random datasets with varying input sizes. You are expected
to measure the average running time of each algorithm by running each experiment 10
times and taking the average of the recorded running times for each input size. Make
sure to save the sorted input data for the next set of experiments. Please be careful that you
measure the running time of the sorting process only. To obtain the input numbers for each
test case of size n, take the first n rows of the given dataset.
Report your findings in milliseconds (ms) by filling out the first three empty rows in Table
3.
Table 3: Results of the running time tests performed for varying input sizes (in ms).
Input Size n
Algorithm 500 1000 2000 4000 8000 16000 32000 64000 128000 250000
Random Input Data Timing Results in ms
Selection sort
Quick sort
Bucket sort
Sorted Input Data Timing Results in ms
Selection sort
Quick sort
Bucket sort
Reversely Sorted Input Data Timing Results in ms
Selection sort
Quick sort
Bucket sort
Experiments on the Sorted Data In this second set of experiments, you should run
your algorithms all over again, but this time on the already sorted input data that you
obtained in the previous experiments. The same averaging rule over 10 tries should
also be applied in this step. Fill out the next three empty rows in Table 3 with the new
measured running times for the sorted input data.
Experiments on the Reversely Sorted Data In this third set of experiments, you should
run your algorithms on the reversely sorted input data. You should use the already sorted
input data that you obtained in the previous experiments and reverse them first (or simply
read the sorted array from the end). Please make sure that you measure the running
time of the sorting process only. The same averaging rule over 10 tries should
also be applied in this step. Fill out the final three empty rows in Table 3 with the new
measured running times for the reversely sorted input data.
BBM204 Programming Assignment 1 7
Spring 2023
BBM204 Software Laboratory II
3.4.2 Experiments with Searching Algorithms
In this set of experiments, you will run the given search algorithms on different input types
and sizes.
Experiments on the Given Random Data In the set of experiments, you will test
the linear search algorithm on the given random datasets with varying input sizes. You
are expected to measure the average running time of each algorithm by running each
experiment 1000 times and taking the average of the recorded running times for
each input size. Use nanosecond precision instead of milliseconds.
Fill out the first row of Table 4 with the new measured running times.
Table 4: Results of the running time tests of search algorithms of varying sizes (in ns).
Input Size n
Algorithm 500 1000 2000 4000 8000 16000 32000 64000 128000 250000
Linear search (random data)
Linear search (sorted data)
Binary search (sorted data)
Experiments on the Sorted Data In the final set of experiments, you will test both
linear and binary search algorithms on the already sorted input data that you obtained in the
previous experiments (do not sort the data again, you should already have saved the sorted
data). Please make sure that you measure the running time of the searching process
only. The same averaging rule over 1000 tries given above should also be applied
in this step.
ò
To perform a searching experiment (e.g., linear search on random data on an
array with 500 elements), pick a random number from the array (from the 500
selected elements) and search for it. Repeat this 1000 times and calculate the
average timing in nanoseconds.
Fill out the remaining rows of Table 4 with the new measured running times.
3.4.3 Complexity Analysis and Result Plotting
After completing all the tests, you should analyze the obtained results in terms of the computational and auxiliary space complexity of the given algorithms. First, complete Tables 5
and 6, and justify your answers in short. Note that we are not interested in the overall space
complexity of these algorithms, only in the additional memory space they use while performing the sorting/searching operations. Please state which lines from the given pseudocodes
you used to obtain the auxiliary space complexity answers.
Plot the results obtained from the experiments in 3.4.1 and 3.4.2. You should obtain four
separate plots for each set of experiments, each of which should include the results for
all given algorithms noted in the result tables. Table 3 should result in three plots, while the
results shown in Table 4 should be plotted as a single chart. If you think that some results
should be plotted separately for better illustration, you are allowed to create extra plots. For
BBM204 Programming Assignment 1 8
Spring 2023
BBM204 Software Laboratory II
Table 5: Computational complexity comparison of the given algorithms.
Algorithm Best Case Average Case Worst Case
Selection Sort Ω(n
2
) Θ(n
2
) O(n
2
)
Quick Sort Ω(n log n) Θ(n log n) O(n
2
)
Bucket Sort
Linear Search
Binary Search
Table 6: Auxiliary space complexity of the given algorithms.
Algorithm Auxiliary Space
Complexity
Selection Sort O(1)
Quick Sort O(n)
Bucket Sort
Linear Search
Binary Search
all plots, X-axis should represent the input size (the number of input instances n), while
Y -axis should represent the running time in ms. See Figure 2 to see an example of how you
should demonstrate your results.
Figure 2: A sample plot showing running time results for varying input sizes on random input
data for two sample sorting algorithms.
BBM204 Programming Assignment 1 9
Spring 2023
BBM204 Software Laboratory II
The sample chart includes two different plotted algorithms, and illustrate how the performance
of a faster algorithm on average can degrade significantly in some worst case scenarios. Your
plots must include the results of all given algorithms presented in a similar manner.
The plotting operation must be handled programmatically by using a readily-made Java
library. You are encouraged to use the XChart library, which is open-source and pretty
easy to use. To use the XChart library, you should first obtain the .zip file by using the
download button from the following link https://knowm.org/open-source/xchart/.
Then, you should extract the file and add xchart-3.8.1.jar to your project; i.e., include it
in your classpath. You can check the example code provided by the authors from the link:
https://knowm.org/open-source/xchart/xchart-example-code/.
3.4.4 Results Analysis and Discussion
Briefly discuss the obtained results by referring to Table 5 and the obtained plots in 3.4.3.
Answer the following questions:
• What are the best, average, and worst cases for the given algorithms in terms of the
given input data to be sorted/searched?
• Do the obtained results (running times of your algorithm implementations) match their
theoretical asymptotic complexities?
Grading Policy
• Submission: 1%
• Implementation of the algorithms: 20%
• Performing the experiments and reporting the results (filling out the given two results
tables): 30%
• Completing the given two computational and auxiliary space complexity tables: 9%
• Plotting the results (at least four plots): 30%
• Results analysis and discussion: 10%
What to Include in the Report
You are encouraged to use this Programming Assignment Report Template and create
your reports in LATEX. We suggest using Overleaf platform for this. This is not mandatory,
but make sure your report has all necessary parts and information (click here to see the PDF
example).
Your report needs to include the following:
1. Include a brief problem statement.
2. Include your Java codes corresponding to the given sorting and search algorithms.
3. Include all running time results tables corresponding to all given experiment sets performed on the given random, sorted, and reversely sorted data, for varying input sizes.
All five algorithms must be tested.
BBM204 Programming Assignment 1 10
Spring 2023
BBM204 Software Laboratory II
4. Include two completed tables that show the theoretical computational and auxiliary
space complexities of the given algorithms, with a brief justification of your answers.
5. Include at least four plots of the obtained results from step 3.
6. Briefly discuss the obtained results by answering the given questions.
7. You may use any theoretical resources, online or otherwise, but make sure to include
the references in your report. Do not copy any ready codes from the internet as
there is a big chance someone else could do the same thing, and you would
get caught for cheating even if you don’t know each other!
Important Notes
• Do not miss the deadline: Thursday, 30.03.2023 (23:59:59).
• Save all your work until the assignment is graded.
• The assignment solution you submit must be your original, individual work. Duplicate
or similar assignments are both going to be considered as cheating.
• You can ask your questions via Piazza (https://piazza.com/hacettepe.edu.
tr/spring2023/bbm204), and you are supposed to be aware of everything discussed
on Piazza.
• You will submit your work via https://submit.cs.hacettepe.edu.tr/ with the
file hierarchy given below:
b<studentID>.zip
src.zip <FILE>
Main.java <FILE>
*.java <FILE>
report.pdf <FILE>
• The name of the main class that contains the main method should be Main.java. You
may use this starter code which has a helpful example of using XChart library. The
main class and all other classes should be placed directly (no subfolders) into a zip file
named src.zip.
• This file hierarchy must be zipped before submitted (not .rar, only .zip files are supported).

References
[1] “Sorting algorithm.” Wikipedia, https://en.wikipedia.org/wiki/Sorting_
algorithm, Last Accessed: 10/02/2022.
[2] N. Faujdar and S. P. Ghrera, “Analysis and Testing of Sorting Algorithms on a Standard
Dataset,” 2015 Fifth International Conference on Communication Systems and Network
Technologies, 2015, pp. 962-967.
[3] G. Batista, “Big O,” Towards Data Science, Nov 5. 2018, https://
towardsdatascience.com/big-o-d13a8b1068c8, Last Accessed: 10/03/2023.
BBM204 Programming Assignment 1 12