Filter Sort Is Ω(N³) in the Worst Case

Non-dominated sorting is a crucial operation used in many popular evolutionary multiobjective algorithms. The problem of non-dominated sorting, although solvable in polynomial time, is surprisingly difficult, and no algorithm is yet known which solves any instance on N points and M objectives in time asymptotically smaller than MN².

For this reason, many algorithm designers concentrate on reducing the leading constant and on (implicitly) tailoring their algorithms to inputs typical to evolutionary computation. While doing that, they sometimes forget to ensure that the worst-case running time of their algorithm is still O(MN²). This is undesirable, especially if the inputs which make the algorithm work too slow can occur spontaneously. However, even if a counterexample is hard to find, the fact that it exists is still a weak point, as this can be exploited and lead to denial of service and other kinds of misbehaving.

In this paper we prove that a recent algorithm for non-dominated sorting, called Filter Sort, has the worst-case complexity of Ω(N³). In particular, we present a scenario which requires Filter Sort to perform Θ(N³) dominance comparisons, where each comparison, however, needs only O(1) elementary operations. Our scenario contains Θ(N) non-domination layers, which is a necessary, but by no means a sufficient condition for being difficult for Filter Sort.