Skip to main content

Table 1 Complexities of \({\mathbf{pf}}\) operators

From: Pareto optimization in algebraic dynamic programming

Operator

Worst case

Expected case

\({\mathbf{pf}}_\text {sort}\)

\(O(N \log N)\)

\(O(N \log N)\)

\({\mathbf{pf}}_\text {isort}\)

\(O(N^2)\)

\(O(N \log N)\)

\({\mathbf{pf}}_\text {lex}\)

O(N)

O(N)

\({\mathbf{pf}}_\text {smooth}\)

\(O(N^2)\)

\(O(N \log N)\)

\({\mathbf {pf}}_\text {nosort}\)

\(O(N^2)\)

\(O(N \log N)\)