R Data Structures and Algorithms

Lower bounds for sorting

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