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)\) |