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

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 important for dealing with large amount of data in real world applications like banks database, schools, etc.

 

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(n2)and quicksort with worst case complexity ofO(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:

Processor: Intel(R) Core (TM) i5-3320M CPU @ 2.60GHz

Installed RAM: 4.00 GB (3.73 GB usable)

System type: 64-bit operating system

Pen and Touch: Touch support with 2 touch points

Computer 2:

Processor:  Intel(R) Core (TM)i7-4770k- CPU@3.50 GHz

Installed RAM: 16GB

System Type: 64-bit operating system

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 < length -1; i++){

if(a[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 ; j1++);
for(; a[j2] >= 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 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

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.

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. 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.