If unsure, shuffle: deductive sort is Θ(MN3), but O(MN2) in expectation over input permutations

Despite significant advantages in theory of evolutionary computation, many papers related to evolutionary algorithms still lack proper analysis and limit themselves by rather vague reflections on why making a certain design choice improves the performance. While this seems to be unavoidable when talking about the behavior of an evolutionary algorithm on a practical optimization problem, doing the same for computational complexities of parts of evolutionary algorithms is harmful and should be avoided.

Non-dominated sorting is one of such parts, commonly used in various evolutionary multiobjective algorithms. The complexity of the problem as such is not well-understood, and many algorithms were proposed for solving it in recent years. Unfortunately, the analysis of some of them is imperfect. In this paper, we prove that, contrary to what is claimed by its authors, the algorithm known as Deductive Sort has the worst-case time complexity of Θ(MN3), where M is the number of objectives and N is the population size. However, if one shuffles the input, the worst-case expected running time drops down to O(MN2).