NUMERICAL COMPLEXITY STUDY OF SOME SORTING ALGORITHMS

Abstract

The complexity analysis of an algorithm has been reviewed using analytical approach like (Big O) notation. These methods do not bring out the differences in complexity. Two or more sorting algorithms may have the same complexity in the three cases which implies that analytical results are equally efficient, but this may not be so when solved numerically. However, for clarity purposes, the actual complexities of the algorithms should be evaluated to determine the best among them. Hence, this study gives the numerical solution to the complexity of bubble sort, insertion sort, merge sort, and quick sort using a C++ program. From the findings, it is observed that quick sort performs best with minimum run-time irrespective of the data size. Merge sort is better than insertion sort and bubble sort. As the data volume continues to increase, bubble sort tends to be faster than insertion sort.