Algorithm Time-Complexity Lab Report

Running Head: COMPARING ALGORITHM TIME COMPLEXITIES
A Detailed Comparison of the Time Complexities of Two Algorithms
with Varying Mathematical Structure
Arleny Paulino, Tamara Pando, Taiseer Uddin, David Jimenez
City College of New York
2
Abstract
The objective of this experiment is to analyze the running time of two sorting algorithms,
bubblesort and quicksort. The implementation was written in C++ using arrays of randomized
integers of 10K, 50K and 100K elements. Due to the different time complexities of bubblesort
O(n^2) and quicksort O(nlogn) we can observe that the quadratic growth of bubblesort takes
significantly longer to sort longer arrays than quicksort. At 10K elements, there was little to no
difference in the processing time for both algorithms but as we incremented the elements to
100K the processing time was significantly slower for bubblesort than quicksort which continued
its normal running time. The efficiency of these two algorithms is imp
3
Introduction
The study of sorting algorithms and their time complexity has been of great importance in the
world of data information and computer science. Sorting data in numerical or lexicographical
order can help us locate specific pieces of information in large databases such as patient lists at
hospitals, students information at schools and financial details in banks instantaneously. In this
lab we will test the efficiency of two sorting algorithms of different time complexities (Cormen
et al, 2001, pg 43), bubblesort having a worse case processing time of O(n ) and quicksort with 2
worst case complexity of O(nlogn) . The experiment will be performed using two different
computer processors and arrays of 10,000, 50,000, 100,000 and 500,000 written in C++
programming language.
Methods and Materials (or Equipment)
1. Two different processors will be used in this experiment:
Computer 1: Computer 2:

4
2. Bubblesort and Quicksort algorithms written in C++ (D., G., & P., 2013) .
void bubblesort(int *a, int length){
long i, temp, finished = 0;
while (!finished){
finished = 1;
for(i = 0; i a[i+1]){
temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
finished = 0;
}
}
}
}
void quicksort(int *a, int length){
long i, j1, j2, pivot, tmp;
if(length > 1){
i = randomindex(length);
pivot = a[i]; a[i] = a[length-1];
a[length-1] = pivot;
j1 = 0; j2 = length-1
while(j1 < j2 ){
for(; a[j1] = pivot && j2 > j1; j2– );
if( j1 != j2 ){
tmp = a[j1]; a[j1] = a[j2]; a[j2] = tmp;
}
}
a[length-1] = a[j1]; a[j1] = pivot;
quicksort( a, j1);
quicksort( a +j1+1, length -j1 -1);
}
}
3. The two computers with different processing power will use proper Integrated Development
Environments to run the algorithms shown above.
Experimental Procedure
In order to test both algorithms and their time complexity, we developed a C++ program
which asks for the total number of elements in the array as user input. After the length of the
array is determined, the program will generate random numbers ranging from 0 to 10,000 to
populate the array. The user then will choose to sort the array using Bubblesort or Quicksort
algorithms. On Computer 1, which has slower processing speed (Eijkhout, 2018), we tested both
5
algorithms using arrays with ten thousand, fifty thousand, one hundred thousand and five
hundred thousand elements. We repeated the experiment using Computer 2 (faster processor)
and added a testing subject of one million elements. Our program used system time to calculate
how long it takes to completely sort the array using both algorithms (not program run time), and
we documented this time for each test as follows:
Results
Table 1. Bubblesort Computation Times
Elements 10,000 50,000 100,000 500,000 1,000,000
Computer 1 6.688s 26.385s 73.302s 2799.56 —
Computer 2 0.336s 9.162s 37.464s 1041.18s 3784.31s
Table 2. Quicksort Computation Times
Elements 10,000 50,000 100,000 500,000 1,000,000
Computer 1 4.186s 6.022s 5.295s 4.525s —
Computer 2 0.001s 0.006s 0.012s 0.091s 0.246s
6
Graph 1. Bubblesort vs. Quicksort (Computer 1)
This graph represents the growth in processing time for both algorithms for Computer 1 which uses a
slower processor than Computer 2. The rate of growth of Bubblesort is exponentially larger than
Quicksort as we increase the number of elements to be sorted.
Graph 2. Bubblesort vs. Quicksort
(Computer 2)
Computer 2 shows improved
results due to its processing
capacity. However, the
processing time for Bubblesort
still grows at a large rate
compared to Quicksort which
maintains its average running
time.
Discussion
Table 1 Bubblesort, gives us a clear depiction on how processors with different speeds
affect the algorithms efficiency. Bubblesort, which grows quadratically, was expected to be
slower than Quicksort, however, the slower processing speeds for Computer 1 clearly shows how
much slower can the processing time of the algorithm be affected relative to other more
advanced equipment. In other words, algorithms will perform better with a newer machine and
an advanced processor.
7
Table 1 and Table 2 compare the performance of both algorithms using the same amount
of elements for both. Initially, the running time difference wasn’t significant, both algorithms
sorted arrays of 10,000 elements at almost the same time. However, as the number of elements
we put in increased, the change in time performance was drastic. Quicksort was able to sort half
a million integers in less than one tenth of a second, while bubblesort took over seventeen
minutes. The experiment was consistent in the different computers that we used. Bubblesort took
substantially more time when compared with quicksort, regardless of the processing power the
computer had. The efficiency of quicksort was even more apparent when we perform quicksort
with 1,000,000 elements in only 0.2 seconds. This can determine whether quicksort or bubble
sort can be used in a real life settings where the number of data entries would not affect the
efficiency of the sorting procedure (D., G., & P., 2013).
Conclusion
In the lab experiment, quicksort was proven to be the fastest sorting algorithm than
bubblesort. The significance of the lab experiment proves that quicksort could be implemented in
computing systems and databases such as banks, government agencies and even throughout the
internet. Having large amounts of data entries sorted numerically or lexicographically can allow
access to information almost instantaneously. The development of faster and more optimal
algorithms is relevant nowadays because everything we use that has a technological
characteristic is programmed to process hundreds of algorithms in order to function.
8
References
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2001). Introduction to algorithms.
Cambridge, MA: MIT Press.
D., G., & P. (2013). RUN-TIME ANALYSIS FOR SORTING ALGORITHMS. Retrieved
October 2, 2018, from
https://pdfs.semanticscholar.org/186b/18407989d49e8e88fc2f7b46c7a2a376afd1.pdf
Eijkhout, Victor. 1 Single-processor Computing. Retrieved October 2, 2018, from
http://pages.tacc.utexas.edu/~eijkhout/istc/html/sequential.html
Sedgewick,Robert.Wayne, Kevin.(2011). Sorting. Algorithms(4th Edition).
Massachusetts.Addison Wesley..https://algs4.cs.princeton.edu/23quicksort/
Photo Credits:
Computer 1, Tamara Pando
Computer 2, David Jimenez

This entry is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International license.