So far, we have covered performance assessment of algorithms based on their time complexity (number of operations). Empirical analysis shows the performance based on actual system runtime, while asymptotic analysis evaluates the performance based on the number of operations (or comparisons). However, for non-comparison-based sorts, such as bin sort and radix sort, the asymptotic complexity is evaluated using the number of iterations based on the value of specific digits as against the whole element itself. Table 5.3 summarizes the asymptotes of sorting algorithms based on the best, average, and worst-case scenarios depending on their type of sort:

Table 5.3: Asymptotic complexities of various assorting algorithms

Now, let's analyze the complexity induced by the problem (of sorting) itself. The upper bound of the sorting problem is the asymptotic complexity of the fastest known algorithm, whereas the lower bound is the best possible efficiency that can be achieved using any sorting algorithm (also includes algorithms which are not invented yet). Once the lower and upper bounds meet using an algorithm, then we can safely assume that no other algorithm can beat this in terms of efficiency.

The best possible bounds of the current sorting algorithms for a given size of input vector are Ω(n) and O(nlog n). This is because of the following reasons:

To date, no one has ever devised an algorithm which can perform better than the O(nlog n) asymptote in both average and worst-case scenarios owing to the previously mentioned reasons. Thus, for a given worst-case scenario, we can comfortably presume that any sorting algorithm which requires Ω(nlog n) comparisons also requires Ω(nlog n) system runtime, which, in turn, shows that the problem of sorting also requires Ω(nlog n) system runtime. Hence, we can conclude that no comparison-based sorting algorithm with asymptotic complexity of θ(nlog n) can improve more than a constant factor.