Time complexity analysis of the deductive sort in the best case
Sumit Mishra, Ved Prakash · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2021
Non-dominated sorting is one of the important step in multiobjective evolutionary algorithms (MOEAs) which are based on Pareto dominance concept. Though non-dominated sorting can be performed in polynomial time, it remains an asymptotical bottleneck in many of these MOEAs. Here we show that an algorithm, Deductive Sort from the paper "Deductive Sort and Climbing Sort: New Methods for Non-Dominated Sorting" by McClymont et al., has the best-case time complexity of [EQUATION].